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

news/2025/2/8 5:33:13/

目录

二分

数的范围

数的三次方跟

机器人跳跃问题

四平方和

分巧克力

前缀和

前缀和

子矩阵的和

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/news/1570249.html

相关文章

（2024|CVPR，MLLM 幻觉）OPERA：通过过度信任惩罚和回顾分配缓解多模态大型语言模型中的幻觉

（2024|CVPR，MLLM 幻觉）OPERA：通过过度信任惩罚和回顾分配缓解多模态大型语言模型中的幻觉

OPERA: Alleviating Hallucination in Multi-Modal Large Language Models via Over-Trust Penalty and Retrospection-Allocation 目录 1. 引言 2. 相关研究 2.1 多模态大语言模型 2.2 LLM 的幻觉与解决方案 2.3. 语言模型中的解码策略 3. 方法 3.1 MLLM 生成过程 3.2…
阅读更多...
【玩转全栈】----Django模板语法、请求与响应

【玩转全栈】----Django模板语法、请求与响应

目录 一、引言 二、模板语法 三、传参 1、视图函数到模板文件 2、模板文件到视图函数 四、引入静态文件 五、请求与响应 ?1、请求 2、响应 六、综合小案例 1、源码展示 2、注意事项以及部分解释 3、展示 一、引言 像之前那个页面&#xff0c;太过简陋&#xff0c;而且一个完整…
阅读更多...
从0开始达芬奇（4）

从0开始达芬奇（4）

⭐快编界面&#xff08;本节重点&#xff09;&#xff1a; 选择片段C键可以自动调色。&#xff08;YYDS&#xff09; 快编界面中的时间线被放大。 母带监看&#xff0c;所有的素材被合并到一起。 ⭐好处就是鼠标不用动&#xff0c;所有的素材进行回放&#xff0c;打下I点和O…
阅读更多...
【论文阅读】Adversarial Detection: Attacking Object Detection in Real Time

【论文阅读】Adversarial Detection: Attacking Object Detection in Real Time

一、背景 目标检测是无人驾驶以及机器人领域中十分关键的一个子任务&#xff0c;该任务将图像作为输入&#xff0c;检测图像中存在的目标&#xff0c;给定该目标的类别以及用于指示位置的包围框bounding box。针对该任务的攻击大多数使用的是像素级的攻击&#xff0c;该攻击计…
阅读更多...
PHP之hyperf学习笔记

PHP之hyperf学习笔记

Hyperf Model,Dao&#xff0c;Service&#xff0c;Contronller 路由 使用文件来配置路由&#xff0c;就是和laravel一样的 Router::addGroup(["middleware" > ["web", "auth"],"namespace" > "Hyperf\HttpServer\Contr…
阅读更多...
LeetCode：583.两个字符串的删除操作

LeetCode：583.两个字符串的删除操作

跟着carl学算法&#xff0c;本系列博客仅做个人记录&#xff0c;建议大家都去看carl本人的博客&#xff0c;写的真的很好的&#xff01; 代码随想录 LeetCode&#xff1a;583.两个字符串的删除操作 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的…
阅读更多...
2025年02月05日Github流行趋势

2025年02月05日Github流行趋势

项目名称&#xff1a;OCRmyPDF 项目地址url&#xff1a;https://github.com/ocrmypdf/OCRmyPDF项目语言&#xff1a;Python历史star数&#xff1a;15872今日star数&#xff1a;157项目维护者&#xff1a;jbarlow83, fritz-hh, apps/dependabot, mawi12345, mara004项目简介&…
阅读更多...
AI驱动的智能流程自动化是什么

AI驱动的智能流程自动化是什么

在当今快速发展的数字化时代&#xff0c;企业正在寻找更高效、更智能的方式来管理日常运营和复杂任务。其中&#xff0c;“AI驱动的智能流程自动化”&#xff08;Intelligent Process Automation, IPA&#xff09;成为了一个热门趋势。通过结合人工智能&#xff08;AI&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023