【AcWing】蓝桥杯辅导课-二分与前缀和
目录
二分
数的范围
数的三次方跟
机器人跳跃问题
四平方和
分巧克力
前缀和
前缀和
子矩阵的和
K倍区间
激光炸弹
二分
数的范围
789. 数的范围 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, q, k, a[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
for(int i = 0;i < n;i ++) cin >> a[i];
while(q --)
{
cin >> k;
int l = 0, r = n - 1;
// 先找左端点
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] < k) l = mid + 1;
else r = mid;
}
if(a[l] != k) cout << "-1 -1" << '\n';
else
{
cout << l << ' ';
l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] > k) r = mid - 1;
else l = mid;
}
cout << r << '\n';
}
}
return 0;
}数的三次方跟
790. 数的三次方根 - AcWing题库
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
double n; cin >> n;
double l = -10000, r = 10000;
while(r - l > 1e-8)
{
double mid = (l + r) / 2;
if(mid * mid * mid < n) l = mid;
else r = mid;
}
cout << fixed << setprecision(6) << l << '\n';
return 0;
}机器人跳跃问题
730. 机器人跳跃问题 - AcWing题库
这道题是一个求最值的问题，我们在求最值时，通常是二分->dfs->dp->贪心。
二分的重点是看是否有二段性。在很多情况下，二分不仅仅只有二段性，还有单调性，但是没有单调性也可能可以使用二分做，只要有二段性即可，有单调性就一定有二段性。
H(k + 1) > E -> E - (H(k + 1) - E) = 2*E - H(k + 1)
H(k + 1) <= E -> E + E - H(k + 1) = 2*E - H(k + 1)
会发现无论当前剩余能量大于、小于或等于下一个建筑的能力值，新能量值的计算方法是一样的
有了这个计算公式之后。假设起始的最低能力值是E0，也就是说2*E0 - H(k + 1)始终能够大于等于0，若E >= E0，则一定有2*E0 - H(k + 1) >= 0；若E < E0，则一定有2*E0 - H(k + 1) < 0
这样我们就找到了二段性，即这道题可以使用二分来解
如何验证当前的mid是否可行呢？
只需要使用当前的mid去递推一遍，看中间是否有小于0的即可
刚开始二分时，l和r分别要是多少呢？
当数组中全是0时，可以取到初始能量值的最小值，也就是0，所以l从0开始
假设数组中的最大值是hm，当我们当前剩余能力E>=hm时，可以利用放缩
跳到下一个建筑物后剩余能量 = E + E - H(k + 1) >= E + hm - H(k + 1) >= E
也就是说，当某一时刻剩余能量大于等于数组H的最大值时，就不需要计算了，因为往后
2*E - H(k + 1)一定大于等于E，也就是大于等于0。所以，r直接从hm开始即可。
因为h[i]的最大值是10^5，而当前剩余能量E只要大于hm就可以不需要计算，所以2*E一定不会超过int的范围，所以不需要开long long
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], n, m;
bool check(int mid)
{
for(int i = 1;i <= n;i ++)
{
mid = 2 * mid - h[i];
if(mid >= m) return true; // 当大于数组最大值时返回true
if(mid < 0) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i ++)
{
cin >> h[i];
if(h[i] > m) m = h[i];
}
int l = 0, r = m;
while(l < r)
{
int mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << '\n';
return 0;
}四平方和
AcWing 1221. 四平方和 - AcWing
这道题很容易就能想到暴力做法，枚举a，b，c三个数，再直接计算出d，因为n的最大值是5*10^6，所以a，b，c，d的最大值约为2232，时间复杂度是高于10^8，所以不行。
由于时间复杂度是原因，最多只能枚举两个数，此时可以考虑空间换时间。我们先两层for循环枚举出c^2+d^2，然后将c^2+d^2的结果保存起来，完成之后，再来两层for循环枚举a^2+b^2，然后根据目标值n及a^2+b^2的结果，去找是否有对于的c^2+d^2。判断一个数在一个集合中是否出现过，就可以使用哈希或者二分。
注意：一个数的表示方法是不唯一的，这道题要求我们输出字典序最小的一组，在循环过程中，a和b，c和d都是按照字典序最小排的，但是两者的组合不一定是按照字典序的组合来排序的，所以，我们在存储c^2+d^2时，不能只存储平方和，还需要将c和d都存储起来，直接存储成一个结构体即可
二分
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2500010;
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 n, m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int c = 0; c * c <= n; c ++ )
for (int d = c; c * c + d * d <= n; d ++ )
sum[m ++ ] = {c * c + d * d, c, d};
sort(sum, sum + m);
for (int a = 0; a * a <= n; a ++ )
for (int b = 0; a * a + b * b <= n; b ++ )
{
int t = n - a * a - b * b;
int l = 0, r = m - 1;
while (l < r) // 查找c^2+d^2中是否有与t相等的
{
int mid = l + r >> 1;
if (sum[mid].s >= t) r = mid;
else l = mid + 1;
}
if (sum[l].s == t)
{
cout << a << ' ' << b << ' ' << sum[l].c << ' ' << sum[l].d << '\n';
return 0;
}
}
return 0;
}哈希表
#include <iostream>
using namespace std;
const int N = 5e6 + 10;
bool flag[N];
int C[N], D[N];
int n, m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
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 (!flag[t])
{
C[t] = c, D[t] = d;
flag[t] = true;
}
}
for (int a = 0; a * a <= n; a++)
for (int b = 0; a * a + b * b <= n; b++)
{
int t = n - a * a - b * b;
if (flag[t])
{
cout << a << ' ' << b << ' ' << C[t] << ' ' << D[t] << '\n';
return 0;
}
}
return 0;
}分巧克力
1227. 分巧克力 - AcWing题库
这道题是很容易找到二段性的，在1到x之间都是能够切出来的，在x+1到1e5之间是切不出来的，而我们要求的答案就是x，所以此时可以直接使用二分
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, k, h[N], w[N];
bool check(int mid)
{
// 看所有的巧克力中，能否切下k个边长为mid的正方形
int sum = 0;
for(int i = 0;i < n;i ++)
{
sum += (w[i] / mid) * (h[i] / mid);//每一大块可以分成的边长为 mid 的巧克力数量
if (sum >= k) return true;//大于要求数量，返回真
}
return false;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
int l = 1, r = 1e5;
for(int i = 0;i < n;i ++) cin >> h[i] >> w[i];
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
return 0;
}前缀和
前缀和
795. 前缀和 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m, l, r, a[N], s[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= n;i ++) s[i] = s[i - 1] + a[i];
while(m --)
{
cin >> l >> r;
cout << s[r] - s[l - 1] << '\n';
}
return 0;
}子矩阵的和
796. 子矩阵的和 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1010;
int n, m, q, x1, x2, y1, y2, a[N][N], s[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
cin >> a[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
while(q --)
{
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << '\n';
}
return 0;
}K倍区间
1230. K倍区间 - AcWing题库
这道题最容易想到的就是直接暴力枚举区间
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k, a[N];
LL ans;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int r = 1;r <= n;r ++)
for(int l = 1;l <= r;l ++)
{
int t = 0;
for(int i = l;i <= r;i ++) t += a[i];
if(t % k == 0) ans ++;
}
cout << ans << '\n';
return 0;
}此时时间复杂度是O(N^3)，N的最大值是10^5，会超时
此时我们会发现，最里面一层循环是求下标为[l, r]这个区间的和，所以可以使用前缀和来进行优化
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
LL s[N], ans;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i ++)
{
cin >> s[i];
s[i] += s[i - 1];
}
for(int r = 1;r <= n;r ++)
for(int l = 0;l < r;l ++)
{
if((s[r] - s[l]) % k == 0) ans ++;
}
cout << ans << '\n';
return 0;
}此时时间复杂度优化到了O(N^2)，还是不行。
我们看两层循环中，里面的那一层循环，这一层循环的意思就是当区间右端点r固定时，左区间端点为0 - r-1中，有几个s[l] % k的余数与s[r] % k的余数相同的。所以，我们此时可以去掉这一层循环，维护一个cnt数组，cnt[i]表示r之前的前缀和中%k余数为i的数的个数
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
LL s[N], cnt[N], ans;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i ++)
{
cin >> s[i];
s[i] += s[i - 1];
}
cnt[0] = 1; // cnt[0]中存的是s[]中等于0的数的个数 由于s[0] = 0 所以最初等于0的有1个数 所以cnt[0] = 1
for(int i = 1;i <= n;i ++)
{
ans += cnt[s[i] % k];
cnt[s[i] % k] ++;
}
cout << ans << '\n';
return 0;
}激光炸弹
99. 激光炸弹 - AcWing题库
这道题的思路很简单，就是先计算出前缀和，然后取出R*R的区间，取值的最大值即可。唯一需要注意的就是R可能很大，需要防止数组越界
#include<iostream>
using namespace std;
const int N = 5010;
int cnt, n, r, x, y, w, s[N][N]; // s数组存放的是前缀和
long long ans;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> cnt >> r;
if(r > 5001) r = 5001; // r再大是没有意义的，为了防止数组越界，取5001与r的最小值
int n = r, m = r; // n表示的是用到的最大的横坐标与r的较大值，m是纵坐标
while (cnt--)
{
cin >> x >> y >> w;
x++, y++;
if (x > n) n = x;
if (y > m) 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];
}
// 取前缀和中R*R区间的最大值
for (int i = r; i <= n; i++)
for (int j = r; j <= m; j++)
{
int t = s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r];
if (t > ans) ans = t;
}
cout << ans << '\n';
return 0;
}