二分与前缀和

🍈前言

❤二分

🌹二分

🌼数的范围

🌼数的三次方根

🌼特殊数字

🌼机器人跳跃问题

🌼四平方和

🌼分巧克力

🌹前缀和

🌼前缀和

🌼子矩阵的和

🌼激光炸弹

🌼K倍区间

🍈前言

❤二分

整数二分模板中，一个比较坑的点，就是C++整数向下取整的机制，考虑到这点，你才能写出AC 100%的代码

关键在于

1，对if ()后面条件的判断

2，条件判断后，是先 l = mid，还是先 r = mid，如果是 l = mid，上面 mid = (l + r + 1) >> 1

3，纸上画图分析目标值和区间的关系

4，避开下取整的坑，就能防止死循环或查找不到目标点

步骤

（1）区间

（2）二段性

（3）分界点

（整数二分边界：区间只剩1个数）

（实数二分边界：区间长度足够小）

🌹二分

🌼数的范围

789. 数的范围 - AcWing题库

一道整数二分的题

AC 代码

#include<iostream>
using namespace std;int main()
{int n, q, k;cin>>n>>q;int a[n + 1];for (int i = 0; i < n; ++i)cin>>a[i];for (int i = 0; i < q; ++i) {cin>>k;// 二分左端点int l = 0, r = n - 1; // 区间范围while (l < r) {int mid = (l + r) >> 1;if (a[mid] >= k) r = mid;elsel = mid + 1;}if (a[r] == k) {cout<<r<<' '; // 退出循环时 l == r// 二分右端点l = r, r = n - 1;while (l < r) {int mid = (l + r + 1) >> 1; // l = mid，考虑到向下取整，mid要先+1if (a[mid] <= k)l = mid;elser = mid - 1; // 目标值必然在r左边, 不包括r}cout<<r<<endl; // 退出循环时 l == r}elsecout<<"-1 -1"<<endl;}return 0;
}

🌼数的三次方根

一道实数二分的题

有单调性一定可以二分，没有单调性也可能可以二分。

（1）确定区间

（2）二段性

（3）边界
（4）注意double以及精度 <1e-8，以便保证6位小数的精度

AC 代码

#include<iostream>
#include<cstdio>
using namespace std;int main()
{double n;cin>>n;double l = -50, r = 50; // 50的三次方已经超过10000了, 主要左端点是负数while (r - l >= 1e-8) {double m = (l + r) / 2;if (m*m*m >= n) r = m;elsel = m;}printf("%.6lf", l);return 0;
}

🌼特殊数字

P1817 - [NewOJ Week 6] 特殊数字 - New Online Judge (ecustacm.cn)

1，两层for里最好遍历到 < 32，才能AC 100%，遍历到 < 31只能AC 67%

虽然2^30已经满足1e9了，不知道为什么不让过，总之范围大一点安全

2，先排序，再二分（因为二分需要二段性和边界）

3，用二分模板，最后需要分类讨论输入的 x 和数组中元素的大小对比

AC 代码

#include<iostream>
#include<algorithm>
using namespace std;int a[1010], cnt; int main()
{// 预处理符合题目要求的二进制数字for (int i = 0; i < 32; ++i)for (int j = i + 1; j < 32; ++j) {a[cnt++] = (1 << i) + (1 << j);}// 先排序再二分sort(a, a + cnt);int t, x;cin>>t;while (t--) {cin>>x;// 二分int l = 0, r = cnt - 1; // 数组下标while (l < r) {int m = (l + r) >> 1;if (a[m] >= x)r = m;elsel = m + 1;} // 退出循环后 l == rif (a[l] == x)cout<<0<<endl;else {int ans;if (a[l] > x)ans = (a[l] - x > x - a[l - 1]) ? x - a[l - 1] : a[l] - x;elseans = (x - a[l] > a[l + 1] - x) ? a[l + 1] - x : x - a[l];cout<<ans<<endl;}}return 0;
}// 1 2 4 8 16 32
// 3 5 6 9 10 12 17 18 20 24 33 34 36 40 48

🌼机器人跳跃问题

730. 机器人跳跃问题 - AcWing题库

（1）

首先，为了确保二段性，我们用归纳法，可以得到，当初始能量 >= 某个值，能量继续增大，还是满足条件

可以用二分

（2）

建议画图分析 while(l < r) 循环内部的操作

AC 代码

#include<iostream>
#include<cstdio>
using namespace std;int n, h[100010];bool check(int x)
{for (int i = 1; i <= n; ++i) {x = 2*x - h[i];if (x < 0) return false;if (x >= 1e5) return true; // 这里剪枝很重要，否则会爆long long}return true;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d", &h[i]);int l = 0, r = 100000;while(l < r) {int m = (l + r) >> 1;if (check(m)) r = m;else l = m + 1;}printf("%d", l);return 0;
}

🌼四平方和

1221. 四平方和 - AcWing题库

（1）每次做题前，先分析时间复杂度，本题 N <= 5e6，因为是平方，每个数最大 2400

（2）考虑到一般空间复杂度要求 1e9，时间复杂度要求1e8，此处只能枚举2个数

（3）N = a^2 + b^2 + c^2 + d^2，枚举a，b后，d = 根号(N - a^2 - b^2 - c^2)，还有个c需要通过空间换时间得到

（4）具体就是
for       a.......for         b......... {t = N - a^2 - b^2;// 二分: 检查t是否在前面出现过O(logn)}
二分前，需要将所有数存在数组中，然后排序

（5）题目中联合主键顺序，即字典序最小

（6）代码中结构体Sum中定义了运算符重载👇

operator< 函数是一个比较运算符，它定义了Sum类型之间的小于关系。当我们使用sort等算法对Sum类型的数组进行排序时，实际上是按照<号运算符的比较结果来确定元素之间的相对位置

字典序最小的解释

（1）由于a从0开始遍历，每一种符合a = 0的可能都会遍历到，所以a是最小的

（2）同理，b从a开始，b一定是第二小的

（3）最后的c, d，定义一个结构体，按 s, c, d优先级的顺序小到大即可

AC 代码

#include<iostream>
#include<algorithm> //sort()
using namespace std;const int N = 2500000;struct Sum {int s, c, d; // 与预处理传入的一一对应bool operator <(const Sum &t)const // 结构体中重载 <{if (s != t.s) return s < t.s;if (c != t.c) return c < t.c;return d < t.d;}
}Sum[N];int main()
{int n, m = 0;cin>>n;// 空间换时间，预处理两个数的平方和for (int c = 0; c*c <= n; ++c)for (int d = c; d*d + c*c <= n; ++d)Sum[m++] = {c*c + d*d, c, d}; // 与定义处一一对应sort(Sum, Sum + m);// 枚举a, bfor (int a = 0; a*a <= n; ++a)for (int b = a; a*a + b*b <= n; ++b) {// 二分: Sum中找c*c + d*dint t = n - a*a - b*b;int l = 0, r = m - 1; // Sum[]的下标while (l < r) {int mid = (l + r) >> 1;if (Sum[mid].s >= t) r = mid;else l = mid + 1;} // 退出循环时, l == rif (Sum[l].s == t) {cout<<a<<" "<<b<<" "<<Sum[l].c<<" "<<Sum[l].d<<endl;return 0;}}return 0;
}

🌼分巧克力

1227. 分巧克力 - AcWing题库

AC 代码

#include<iostream>
#include<cstdio> // scanf(), printf()
using namespace std;const int N = 100005;
int n, k, h[N], w[N];bool check(int m)
{int res = 0;for (int i = 0; i < n; ++i) {res += (h[i] / m) * (w[i] / m);if (res >= k) return true; // 剪枝}return false;
}int main()
{scanf("%d %d", &n, &k);for (int i = 0; i < n; ++i) scanf("%d %d", &h[i], &w[i]);int l = 0, r = 1e5;while (l < r) {int m = (l + r + 1) >> 1; // m表示边长if (check(m)) // check 表示个数l = m;elser = m - 1;}printf("%d", l);return 0;
}

🌹前缀和

🌼前缀和

795. 前缀和 - AcWing题库

AC 代码

#include<iostream>
#include<cstdio> 
using namespace std;const int N = 100005;int main()
{int n, m, a[N], s[N] = {0};scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);s[i] += s[i - 1] + a[i];   }int l, r;while (m--) {scanf("%d%d", &l, &r);printf("%d\n", s[r] - s[l - 1]);}return 0;
}

🌼子矩阵的和

796. 子矩阵的和 - AcWing题库

画图，容斥原理

（1）预处理前缀和数组👇

S(i, j) = S(i - 1, j) + S(i, j - 1) - S(i - 1, j - 1) + a(i, j)

（2）利用前缀和数组计算ans

ans = S(x2 , y2) - S(x2, y1 - 1) - S(x1 - 1, y2) + S(x1 - 1, y1 - 1)

（3）为防止越界，下标从 1~n

AC 代码

#include<iostream>
#include<cstdio>const int N = 1005;int main()
{int n, m, q, a[N][N], s[N][N];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[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);}return 0;
}

🌼激光炸弹

99. 激光炸弹 - AcWing题库

注意目标位置，可以理解为在点上。

在上题容斥原理的基础上，O( (n - R + 1) * (n - R + 1) )，枚举正方形右下角的点。

本题难点在于边界，而不是二维前缀和

再说说空间复杂度👇

5000 * 5000二维数组 int，= 2.5 * 10^7，两个二维数组a[][] 和 s[][] 就是 5 * 10^7

1 int = 4 byte

= 2 * 10^8 byte

1M = 1024 * 1024 byte

所以2个二维开到 2 * 10^8 / 10^6 = 200M > 168M

所以只能开1个 s[][]

tips: 为了防止初始越界，前缀和类型都从1开始

已经得到前缀和矩阵，如何计算ans，参考上题截图👇

AC 代码

有几个坑，详情看注释

#include<iostream>
#include<algorithm> //max()
using namespace std;const int N = 5010;int main()
{int cnt, R, s[N][N] = {0};cin>>cnt>>R;R = min(R, 5001); // 防止越界int x, y, w, n, m;n = m = R; // 防止 n, m 为0, 无法进入循环while (cnt--) {cin>>x>>y>>w;x++, y++; // 坐标1开始n = max(n, x), m = max(m, y); // 不越界s[x][y] += w;}// 预处理前缀和数组for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];int ans = 0;// 枚举边长R正方形的右下角(i ,j)for (int i = R; i <= n; ++i)for (int j = R; j <= m; ++j)ans = max(ans, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);cout<<ans<<endl;return 0;
}

🌼K倍区间

1230. K倍区间 - AcWing题库

一维前缀和 + 同余

时间 O(n)

解释下同余👇

cnt[s[i] % k]++; cnt[i] 统计余数为 i 的前缀和的个数

ans += cnt[i]，注意ans放前面，因为先出现余数相同的前缀和，才能 +=

同余意味着，( s[j] - s[i] ) % k == 0，满足题意

AC 代码

#include<iostream>
#include<cstdio>const int N =  100005;
#define LL long longint main()
{LL n, k, s[N] = {0}, cnt[N] = {0}, ans = 0; // LL防止爆intscanf("%lld%lld", &n, &k);// 读入 + 预处理前缀和for (int i = 1; i <= n; ++i) {scanf("%d", &s[i]);s[i] += s[i - 1];}// 同余cnt[0] = 1; // 余数0直接加for (int i = 1; i <= n; ++i) {ans += cnt[s[i] % k]; // 先 ans+=cnt[s[i] % k]++; // 再cnt[]++}printf("%lld", ans);return 0;
}