【AcWing】蓝桥杯辅导课-二分与前缀和

server/2025/2/9 5:38:57/

目录

二分

数的范围

数的三次方跟

机器人跳跃问题

四平方和

分巧克力

前缀和

前缀和

子矩阵的和

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; // 当大于数组最大值时返回trueif(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] = 1for(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;
}


http://www.ppmy.cn/server/166138.html

相关文章

COBOL语言的云计算

COBOL语言的云计算

COBOL语言与云计算&#xff1a;重新定义传统编程的未来 引言 在技术迅速发展的今天&#xff0c;云计算已成为推动企业数字化转型的关键力量。与此同时&#xff0c;许多传统编程语言依然在大型企业中发挥着不可或缺的作用。在这些传统语言中&#xff0c;COBOL&#xff08;Comm…
阅读更多...
101.对称二叉树 python

101.对称二叉树 python

对称二叉树 题目题目描述示例 1&#xff1a;示例 2&#xff1a;提示&#xff1a; 题解递归法步骤提交结果 迭代法步骤提交结果 题目 题目描述 给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出…
阅读更多...
微信小程序地图开发总结-规划路线

微信小程序地图开发总结-规划路线

在现代移动应用中&#xff0c;地图导航功能已成为必不可少的一部分。通过地图 API&#xff0c;我们可以轻松地在应用中集成位置服务和路径规划功能。本篇文章将带大家一起实现一个简单的路径导航功能&#xff0c;使用腾讯地图 API结合微信小程序&#xff0c;实现从当前位置到目…
阅读更多...
企业FTP替代升级，实现传输大文件提升100倍！

企业FTP替代升级，实现传输大文件提升100倍！

随着信息技术的飞速发展&#xff0c;网络安全环境也变得越来越复杂。在这种背景下&#xff0c;传统的FTP&#xff08;文件传输协议&#xff09;已经很难满足现代企业对文件传输的需求了。FTP虽然用起来简单&#xff0c;但它的局限性和安全漏洞让它在面对高效、安全的数据交换时…
阅读更多...
用 Python 给 Excel 表格截图（20250207）

用 Python 给 Excel 表格截图（20250207）

我搜索了网络上的方案&#xff0c;感觉把 Excel 表格转换为 HTML 再用 platwright 截图是比较顺畅的路径&#xff0c;因为有顺畅的工具链。如果使用的是 Windows 系统则不需要阅读此文&#xff0c;因为 win32com 库更方便。这篇文章中 Excel 转 HTML 的方案&#xff0c;主要弥补…
阅读更多...
TaskBuilder项目实战：创建项目

TaskBuilder项目实战：创建项目

用TaskBuilder开发应用系统的第一步就是创建项目&#xff0c;项目可以是一个简单的功能模块&#xff0c;也可以是很多功能模块的集合&#xff0c;具体怎么划分看各位的实际需要&#xff0c;我们一般会将相互关联比较紧密的一组功能模块放到一个独立的项目内&#xff0c;以便打包…
阅读更多...
基于javaweb的SpringBoot小区智慧园区管理系统(源码+文档+部署讲解）

基于javaweb的SpringBoot小区智慧园区管理系统(源码+文档+部署讲解）

&#x1f3ac; 秋野酱&#xff1a;《个人主页》 &#x1f525; 个人专栏:《Java专栏》《Python专栏》 ⛺️心若有所向往,何惧道阻且长 文章目录 运行环境开发工具适用功能说明 运行环境 Java≥8、MySQL≥5.7、Node.js≥14 开发工具 后端&#xff1a;eclipse/idea/myeclipse…
阅读更多...
DeepFM：融合因子分解机与深度学习的CTR预测模型

DeepFM：融合因子分解机与深度学习的CTR预测模型

引言 点击率&#xff08;Click-Through Rate, CTR&#xff09;预测是推荐系统和计算广告领域的核心任务。传统方法通常依赖人工特征工程或单一模型架构&#xff0c;难以同时捕捉低阶与高阶特征交互。为了克服这些限制&#xff0c;研究者们不断探索新的模型架构&#xff0c;以更…
阅读更多...
最新文章

Copyright @ 2022~2023