目录
🍈前言
❤二分
整数二分模板中，一个比较坑的点，就是C++整数向下取整的机制，考虑到这点，你才能写出AC 100%的代码
关键在于
1，对if ()后面条件的判断
2，条件判断后，是先 l = mid，还是先 r = mid，如果是 l = mid，上面 mid = (l + r + 1) >> 1
3，纸上画图分析 目标值 和 区间的关系
4，避开下取整的坑，就能防止死循环 或 查找不到目标点
步骤
（1）区间
（2）二段性
（3）分界点
（整数二分边界：区间只剩1个数）
（实数二分边界：区间长度足够小）
🌹二分
🌼数的范围
一道整数二分的题
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;
else
l = 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要先+1
if (a[mid] <= k)
l = mid;
else
r = mid - 1; // 目标值必然在r左边, 不包括r
}
cout<<r<<endl; // 退出循环时 l == r
}
else
cout<<"-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;
else
l = 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;
else
l = m + 1;
} // 退出循环后 l == r
if (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;
else
ans = (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
🌼机器人跳跃问题
（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;
}🌼四平方和
（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, b
for (int a = 0; a*a <= n; ++a)
for (int b = a; a*a + b*b <= n; ++b) {
// 二分: Sum中找c*c + d*d
int 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 == r
if (Sum[l].s == t) {
cout<<a<<" "<<b<<" "<<Sum[l].c<<" "<<Sum[l].d<<endl;
return 0;
}
}
return 0;
}🌼分巧克力
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;
else
r = m - 1;
}
printf("%d", l);
return 0;
}🌹前缀和
🌼前缀和
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;
}🌼子矩阵的和
画图，容斥原理
（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;
}🌼激光炸弹
注意目标位置，可以理解为在点上。
在上题容斥原理的基础上，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倍区间
一维前缀和 + 同余
时间 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 long
int main()
{
LL n, k, s[N] = {0}, cnt[N] = {0}, ans = 0; // LL防止爆int
scanf("%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;
}
