二分与前缀和
目录
1.数的范围
这个是典型的二分模板，注意边界条件
int mid = l + r >> 1;//这里究竟要不要加1
//数的范围
//典型整数二分模板
#include<bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int n, T;
int q[N];
int main()
{
scanf("%d%d", &n, &T);
for(int i = 0; i < n; i++) scanf("%d", &q[i]);
while(T --)
{
int k;
cin >> k;
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(q[mid] >= k) r = mid;
else l = mid + 1;
}
if(q[l] != k)
{
puts("-1 -1");
continue;
}
printf("%d ", l);
r = n - 1;//只需要更新r
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= k) l = mid;
else r = mid - 1;
}
printf("%d\n", l);
}
return 0;
}
2.数的三次方根
实数二分，要比整数二分简单不少，注意精度问题，在二分的时候比要求的精度高两位
//数的三次方根
// 实数二分
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
int main()
{
double x;
cin >> x;
double l = -10000, r = 10000;
while(r - l > eps)
{
double mid = (l + r) / 2;
if(mid * mid * mid > x) r = mid;
else l = mid;
}
printf("%.6lf\n", l);
return 0;
}
3.前缀和
//前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i - 1];
}
while(m --)
{
int l, r;
cin >> l >> r;
cout << a[r] - a[l - 1] << endl;
}
return 0;
}
4.子矩阵的和
二位前缀和，记住公式就行了
//二维前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N];
int get(int x1, int y1, int x2, int y2)
{
return a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1];
}
int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
}
}
while(q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << get(x1, y1, x2, y2) << endl;
}
return 0;
}
5.机器人跳跃问题（二分）
对于这道题目，经过分类讨论，可以得出一个公式。设机器人在第 $i$ 个建筑的位置的时候，机器人的能量为 $E_i$ ，那么第 $i+1$ 个位置时能量为
$$
E_{i+1}=2E_i-H_{i+1}
$$
这是一个递推公式，显然，如果设机器人初始能量值为 $x$，那么：
$$
E_1=2x-H_1
$$
$$ E_2=2E_1-H_2=2(2x-H_1)-H_2=4x-2H_1-H_2 $$
依次类推，机器人在每个建筑物位置的能量都可以计算出来。到这里有两个思考方向。
第一种：递推解方程
- 我是不是可以让每个$E_i>0$然后得到一系列方程把 $x$ 求解出来？
是的，这只是个一元一次不等式，很容易求解
$$
x >= \frac{H_1}{2}
$$
$$ x >= \frac{H_1}{2} + \frac{H_2}{4} $$
$$ x >= \frac{H_1}{2} + \frac{H_2}{4} + \frac{H_3}{8} + …+ \frac{H_n}{2^n} $$
不难发现，只需要把$$\frac{H_1}{2} + \frac{H_2}{4} + \frac{H_3}{8} + …+ \frac{H_n}{2^n}$$求出来就行了，于是，问题得到解决！
代码如下：
//递推解方程
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N];
double p[N];//存放2的次幂
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
p[0] = 1;//2^0=1
double res = 0;
for(int i = 1; i <= n; i++)
{
p[i] = p[i - 1] * 2;
res += 1.0 / p[i] * h[i];
}
cout << ceil(res) << endl;
return 0;
}
第二种方法：二分
接着上面思考，我们得到了公式
$$
E_{i+1}=2E_i-H_{i+1}
$$
如果设机器人初始能量值为 $x$，那么：
$$
E_1=2x-H_1
$$
$$ E_2=2E_1-H_2=2(2x-H_1)-H_2=4x-2H_1-H_2 $$
依次类推，机器人在每个建筑物位置的能量都可以计算出来。
也就是说，给定一个能量值 $x$，很容易判断这个 $x$是不是满足要求的，这是第一个条件。所以暴力枚举一遍x肯定可以求解！恭喜你，找到了一个暴力的做法。
继续思考，如果 $x$ 满足条件，那么所有大于 $x$ 的肯定也满足条件；如果 $x$ 不满足条件，那么所有小于 $x$ 的肯定也不满足条件。我们发现$x$ 满足两段性。于是，自然而然就想到了二分。
//二分求解
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N];
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;//加速
}
return true;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
int l = 1, r = 1e5;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
第三种方法：倒着递推
接着上面思考，我们得到了公式
$$
E_{i+1}=2E_i-H_{i+1}
$$
变形一下可以得到
$$
E_i = \frac{E_{i+1} + H_{i+1}}{2}
$$
可以直观的想象，初始能量值最小（不限于整数）的情况，一定是到达最后一个建筑物时能量值为 $0$ 的情况，由此开始倒退初始能量值，代码如下：
//倒着递推
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
double e = 0;
for(int i = n - 1; i >= 0; i--)
{
e = (h[i + 1] + e) / 2;
}
cout << ceil(e) << endl;
return 0;
}
6.四平方和
这道题目最重要的思路是空间换时间。听我细细道来~
本来，我们需要枚举 $a$, $b$, $c$ , $d$ 四个数字，因为第四个数字可以计算出来，所以至少需要三重循环，即 $ O(n^3)$，但是这肯定是要超时的，所以就想办法优化循环的次数。
一个比较好的思路是把三重循环拆成两次二重循环。在第一次二重循环中，计算一下c^2+d^2,然后记录下来，在第二次对a和b的循环中可以直接使用，而不需要再次计算。如此一来，时间复杂度就被大大的简化了。
至于如何记录 $c^2+d^2$ ，则可以考虑使用哈希表，或者数组+二分的做法。不得不说，实在是太巧妙了！！
1.模拟哈希表
使用C++自带的unordered_map过不了，不过模拟哈希表却可以过。
//四平方和
//模拟哈希表
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 5e6 + 10;
int n;
int r[N * 2];//小技巧，避免pair，r[c^2+d^2]=c;可以推导出d
int main()
{
cin >> n;
memset(r, -1, sizeof r);
for(int c = 0; c * c <= n; c++)
{
for(int d = c; c * c + d * d <= n; d++)
{
int t = c * c + d * d;
if(r[t] == -1)
{
r[t] = c;
}
}
}
for(int a = 0; a * a <= n; a ++)
{
for(int b = a; a * a + b * b <= n; b++)
{
int t = n - a * a - b * b;
int c = r[t];
if(r[t] == -1) continue;
int d = sqrt(t - c * c);
printf("%d %d %d %d\n", a, b, c, d);
return 0;
}
}
return 0;
}
2.二分查找
//四平方和
//二分
#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
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;
}
};
int n;
Sum record[N * 2];
int main()
{
cin >> n;
int k = 0;
for(int c = 0; c * c <= n; c++)
{
for(int d = c; c * c + d * d <= n; d ++)
{
record[k++] = {c * c + d * d, c, d};
}
}
sort(record, record + k);
for(int a = 0; a * a <= n; a ++)
{
for(int b = a; a * a + b * b <= n; b++)
{
int t = n - a * a - b * b;
int l = 0, r = k - 1;
while(l < r)
{
int mid = l + r >> 1;
if(record[mid].s >= t) r = mid;
else l = mid + 1;
}
if(record[l].s == t)
{
printf("%d %d %d %d\n", a, b, record[l].c, record[l].d);
return 0;
}
}
}
return 0;
}
7.分巧克力
找出边界条件，找出计算公式，然后快可以一个一个尝试了，发现可以用二分优化！
//分巧克力 二分
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int h[N], w[N];
bool check(int x)
{
int res = 0;
for(int i = 0; i < n; i++)
{
res += ((h[i]/x)*(w[i]/x));
}
return res >= k;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> h[i] >> w[i];
int l = 0, r = 1e5;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
8.激光炸弹
典型二维前缀和，注意边界就是了。
这道题目的表述很混乱，价值那里没说清楚，读入的时候是+=还是=没讲清楚
另外一个比较坑的地方是如果开两个二维数组，会MLE，只能用一个二维数组
代码如下：
//激光炸弹
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, r, q;//n代表边长,q代表目标数
int g[N][N];
int get(int x1, int y1, int x2, int y2)
{
return g[x2][y2] - g[x2][y1-1] - g[x1-1][y2] + g[x1-1][y1-1];
}
int main()
{
cin >> q >> r;
while(q--)
{
int x, y, w;
cin >> x >> y >> w;
g[x + 1][y + 1] += w;//下标从1开始
n = max(n, max(x + 1, y + 1));
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
}
}
int res = 0;
//枚举起点
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
int x2 = min(n, i + r - 1), y2 = min(n, j + r - 1);
res = max(res, get(i, j, x2, y2));
}
}
cout << res << endl;
return 0;
}
9.K倍区间
首先，这道题目因为这道题目要求 $ A_i,…,A_j$ 之和，所以不难想到前缀和。然后写出下面的暴力做法
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
判断A[i...j]是否符合要求;
这种做法的时间复杂度是 $\color{red}{O(N^2)}$ ，无法通过，所以再想办法优化。
第一种：按公式计算
因为是判断倍数，如果一段区间 $[l…r]$ 满足是 $k$ 的倍数，那么有
$$
S_r\equiv{S_{l-1}}\pmod{k}
$$
变化得到
$$
S_r - S_{l-1}\equiv{0}\pmod{k}
$$
我们可以把所有的前缀和数组都变成模 $k$ 的余数，然后只有余数相等的两个数做差才可能得到一段K倍区间。如果余数为 $a$ 的数字一共有 $t$ 个，那么总共有
$$
C_{t}^2 = \frac{t (t - 1)}{2}
$$
于是，按照该公式计算即可，时间复杂度为 $\color{green}{O(n)}$ ，可以过。
注意：上述计算的是两个数字相减组成的区间，还有一类是单一元素组成的区间，应该加上。在代码中有注释。
//K倍区间
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
LL a[N], cnt[N];
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] = (a[i] + a[i - 1]) % k;
cnt[a[i]]++;
}
LL res = 0;
res += cnt[0];//一个数字组成的我区间
//多个数字组成的区间
for(int i = 0; i < n; i++)
{
if(cnt[i] > 0)
res += cnt[i] * (cnt[i] - 1) / 2;
}
cout << res << endl;
return 0;
}
第2种：直接枚举
对每一个数字，计算它的前面有多少和它同余的数字。我们可以使用一个数组cnt[N]记录上述数据。
for(int i = 1; i <= n; i++)
{
res += cnt[a[i] % k];
}
//注意上面求的区间的长度 >= 2，是由两个数做减法得到的，我们最后还要加上一个数单独组成的区间
res += cnt[0];
具体代码如下：
//K倍区间
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
LL a[N], cnt[N];
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i - 1];
}
LL res = 0;
//计算由两个数相减得到的区间
for(int i = 1; i <= n; i++)
{
res += cnt[a[i] % k];
cnt[a[i] % k]++;
}
//加上一个数的区间
res += cnt[0];
cout << res << endl;
return 0;
}
