整数二分步骤:
整数二分步骤:
1.找一个区间[L，R]，使得答案一定在该区间中
2找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。
3.分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间;如果不成立，考虑答案在哪个区间;
4.如果更新方式写的是R（右） = Mid，则不用做任何处理;如果更新方式写的是L（左）= Mid，则需要在计算Mid时加上1。
AcWing 789. 数的范围 - 整数二分
给定一个按照升序排列的长度为n的整数数组，以及q个查询。
对于每个查询，返回一个元素k的起始位置和终止位置(位置从О开始计数)。如果数组中不存在该元素，则返回-1 -1 。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1～10000范围内)，表示完整数组。接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。如果数组中不存在该元素，则返回-1 -1。
数据范围
1<n ≤100000
1≤q≤10000
1≤k ≤10000
输入样例:
6 3 1 2 2 3 3 4 3 4 5
输出样例：
3 4 5 5 -1 -1
#include<iostream> using namespace std; const int N=100010; int n,m; int q[N]; int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&q[i]); while(m--) { int x; scanf("%d",&x); int l=0,r=n-1; while(l<r) //取始下标 { int mid=l+r>>1; if(q[mid]>=x) r=mid; else l=mid+1; } if(q[l]!=x) cout<<"-1 -1"<<endl; else { cout<<l<<' '; int l=0,r=n-1; while(l<r) //取末下标 { int mid=l+r+1>>1; if(q[mid]<=x) l=mid; else r=mid-1; } cout<<l<<endl; } } return 0; }
记忆：写完模板后看案例分析始末下标，当 l （左）= mid 时必须mid+1
AcWing 790. 数的三次方根 - 实数二分
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。注意，结果保留6位小数。
数据范围
-10000<n≤10000
输入样例：
1000.00
输出样例：
10.000000
#include<iostream> using namespace std; int main() { double l=-100000,r=100000; //数据结果必在其之间，不用思考 double n,m; cin>>n; while(r-l>1e-8) //精确到为1e-6，所以至少要多精确两位 { m=(l+r)/2; if(m*m*m>=n) r=m; //立方根n在mid的左边，缩右边界 else l=m; } printf("%.6f",m); return 0; }
AcWing 730. 机器人跳跃问题 - 二分应用
来源：今日头条2019，笔试题
输入样例1：
1. 5 2. 3 4 3 2 4
输出样例1：
4
输入样例2：
1. 3 2. 4 4 4
输出样例2：
4
输入样例3：
1. 3 2. 1 6 4
输出样例3：
3
思路：
如例一高度 3 4 3 2 4
可以发现通过计算 E=2E-H(k+1)，那么只需要将数组所有值带入公式，找到刚好大于0的E即可；
利用二分，check函数为 将数组所有值带入公式
如果e<0则不满足要求，返回fasle；
如果e大于数组中最大值，由公式E=2E-H(k+1)得，E将永远大于0，可直接返回true（此操作可以防止2E太大爆int，同时可以节省时间）
#include<iostream> #include<cstring> using namespace std; const int N=1e5+10; int n; int h[N]; bool check(int e) { for(int i=1;i<=n;i++) { e=e*2-h[i]; if(e<0) return false; if(e>1e5) return true;//防止爆int } return true; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>h[i]; int l=0,r=1e5; while(l<r) { int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } cout<<l<<endl; return 0; }
总结：
当题目求“至少”、“至多”，且具有二段性or单调性时，可以考虑二分
（二段性：以某个值为临界，这个值一边的都满足要求，另一边都不满足）
AcWing 1227. 分巧克力
来源：第八届蓝桥杯省赛C++A/B组,第八届蓝桥杯省赛JAVAA/B组
输入样例：
1. 2 10 2. 6 5 3. 5 6
输出样例：
2
具有单调性与二段性，用二分！
#include<iostream> using namespace std; int n,k; const int N=1e5+10; int h[N],w[N]; int check(int m) { int ret=0; for(int i=0;i<n;i++) { ret+=(h[i]/m)*(w[i]/m); if(ret>=k) return 1; } return 0; } int main() { cin>>n>>k; for(int i=0;i<n;i++) cin>>h[i]>>w[i]; int l=1,r=1e5; while(l<r) { int mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } cout<<l; return 0; }
AcWing 795. 前缀和
输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l, r。
对于每个询问，输出原序列中从第 l 个数到第r个数的和。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，表示整数数列。
接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。
输出格式
共m行，每行输出一个询问的结果。
数据范围
1≤l<r ≤n，1 ≤n, m ≤100000,
—1000≤数列中元素的值≤1000
输入样例：
5 3 2 1 3 6 4 1 2 1 3 2 4
输出样例：
3 6 10
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int N=1e5+10; int n,m; int a[N]; int s[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; } while(m--) { int l,r; cin>>l>>r; cout<<s[r]-s[l-1]<<endl; } return 0; }
k倍区间
来源：第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组
思路：
区间[l,r]的和是k的倍数即(sum[r] - sum[l-1])%k == 0 即sum[r]%k == sum[l-1]%k ；
简单来讲，sum[r] % k 和 sum[l-1] % k 的余数如果相等，那么sum[r] - sum[l-1]的差值必然是k的倍数 ，比如说：13 % 7 == 20 % 7 等价于(20-13)%7 =0；
ans一开始是表示的相减满足题目的条件，因为一旦再出现%k和res数组里面有相当的情况，就全加一遍（和前面全部组合一遍），然后res【sum【i】】++
cnt[0]=1解释：不置为1的话，那么就少了自身单独一个就可以成立的情况
#include<iostream> using namespace std; typedef long long ll; const int N=1e5+10; int n,k; ll s[N]; int cnt[N]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld",&s[i]); s[i]+=s[i-1]; } ll ans=0; cnt[0]=1; for(int i=1;i<=n;i++) { ans+=cnt[s[i]%k]; cnt[s[i]%k]++; } cout<<ans; return 0; }
另一种思路相同但是更容易理解的方法
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100010; LL a[N],s[N],cnt[N];//cnt计算相同余数的序列的个数总和 //区间[l,r]的和是k的倍数即(sum[r] - sum[l-1])%k == 0 即sum[r]%k == sum[l-1]%k //由这个公式可得，找出余数相同的前缀和然后两两组合一次就是一个k倍区间 int main () { int n,k; cin >> n >> k; LL ans = 0; //ll数据太大 s[0] = 0; //第一项必为0 cnt[0] = 1;//初始化 防止影响结果 S0=0是有意义的 for (int i = 1; i <= n; i ++) { cin >> a[i]; s[i] = (s[i - 1] + a[i]) % k; cnt[s[i]] ++; } for (int i = 0;i < k; i ++) { //余数必在 0~k-1之间 ans += cnt[i] * (cnt[i] - 1) / 2; //数学C n 取 2 的公式 } cout << ans << endl; return 0; }
AcWing 796. 子矩阵的和 - 二维前缀和
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数:x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数n， m，q。
接下来n行，每行包含m个整数，表示整数矩阵。
接下来q行，每行包含四个整数x1,y1,x2,y2，表示一组询问。
输出格式
共q行，每行输出一个询问的结果。
数据范围
1≤n, m ≤1000, 1≤q≤200000, 1≤1 ≤2 ≤n，1≤91≤J2≤m,
-1000≤矩阵内元素的值≤1000
输入样例：
3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4
输出样例：
17 27 21
用容斥原理推出公式；
首先算出每一个坐标的前缀和s [ i ] [ j ]，在前缀和矩阵中再用一次容斥原理
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1010; int n, m, q; int a[N][N], s[N][N]; int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) { scanf("%d", &a[i][j]); s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; } while (q -- ) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); } return 0; }
AcWing 797. 差分
6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1
差分思路：
首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];
然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i];
使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]
即：
a[0 ]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] =a [3] - a[2];
........
b[n] = a[n] - a[n-1];
a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c;
然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;
核心操作：对差分数组b做 b[l] + = c, b[r+1] - = c（时间复杂度为O(1) ）
#include<iostream> using namespace std; const int N = 1e5 + 10; int a[N], b[N]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i] - a[i - 1]; //构建差分数组 } int l, r, c; while (m--) { scanf("%d%d%d", &l, &r, &c); b[l] += c; //将序列中[l, r]之间的每个数都加上c b[r + 1] -= c; } for (int i = 1; i <= n; i++) { a[i] = b[i] + a[i - 1]; //前缀和运算 printf("%d ", a[i]); } return 0; }
AcWing 798. 差分矩阵 - 二维差分
输入样例：
3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1
输出样例：
2 3 4 1 4 3 4 1 2 2 2 2
思路与二维前缀和相似：
操作1、
b[x1][y1] + = c;
b[x1,][y2+1] - = c;
b[x2+1][y1] - = c;
b[x2+1][y2+1] + = c;
每次对b数组执行以上操作，等价于：
for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++) a[i][j]+=c;
操作2、
我们每次让以(i,j)为左上角到以(i,j)为右上角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j]，等价于原数组a中(i,j) 到(i,j)范围内 加上了 a[i][j] ,因此执行n*m次插入操作，就成功构建了差分b数组.
说白了，就是让c=a[i][j]，把操作1的方法用在一个空数组上，用n*m遍，操作完之后这个数组就是差分数组b[i][j]。
for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) insert(i, j, i, j, a[i][j]); //构建差分数组
AC代码：
#include <iostream> using namespace std; const int N = 1010; int n, m, q; int a[N][N], b[N][N]; void insert(int x1, int y1, int x2, int y2, int c) { b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) scanf("%d", &a[i][j]); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) insert(i, j, i, j, a[i][j]); //构建差分数组 while (q -- ) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; insert(x1, y1, x2, y2, c); } for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //a[i]是差分数组b[i]的前缀和 for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]); puts(""); } return 0; }
