二分与前缀和

目录

🍈前言

❤二分

🌹二分

🌼数的范围

🌼数的三次方根

🌼特殊数字

🌼机器人跳跃问题

🌼四平方和

🌼分巧克力

🌹前缀和

🌼前缀和

🌼子矩阵的和

🌼激光炸弹

🌼K倍区间

🍈前言

❤二分

整数二分模板中，一个比较坑的点，就是C++整数向下取整的机制，考虑到这点，你才能写出AC 100%的代码

关键在于

1，对if ()后面条件的判断 

2，条件判断后，是先 l = mid，还是先 r = mid，如果是 l = mid，上面 mid = (l + r + 1) >> 1

3，纸上画图分析 目标值 和 区间的关系

4，避开下取整的坑，就能防止死循环 或 查找不到目标点

步骤

（1）区间

（2）二段性

（3）分界点 

（整数二分边界：区间只剩1个数）

（实数二分边界：区间长度足够小）

🌹二分

🌼数的范围

789. 数的范围 - AcWing题库

一道整数二分的题 

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;elsel = 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要先+1if (a[mid] <= k)l = mid;elser = mid - 1; // 目标值必然在r左边, 不包括r}cout<<r<<endl; // 退出循环时 l == r}elsecout<<"-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;elsel = 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;elsel = m + 1;} // 退出循环后 l == rif (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;elseans = (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

🌼机器人跳跃问题

730. 机器人跳跃问题 - AcWing题库

（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;
}

🌼四平方和

1221. 四平方和 - AcWing题库

（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, bfor (int a = 0; a*a <= n; ++a)for (int b = a; a*a + b*b <= n; ++b) {// 二分: Sum中找c*c + d*dint 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 == rif (Sum[l].s == t) {cout<<a<<" "<<b<<" "<<Sum[l].c<<" "<<Sum[l].d<<endl;return 0;}}return 0;
}

🌼分巧克力

1227. 分巧克力 - AcWing题库

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;elser = m - 1;}printf("%d", l);return 0;
}

🌹前缀和

🌼前缀和

795. 前缀和 - AcWing题库

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;
}

🌼子矩阵的和

796. 子矩阵的和 - AcWing题库

画图，容斥原理

（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;
}

🌼激光炸弹

99. 激光炸弹 - AcWing题库

注意目标位置，可以理解为在点上。

在上题容斥原理的基础上，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倍区间

1230. K倍区间 - AcWing题库

一维前缀和 + 同余

时间 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 longint main()
{LL n, k, s[N] = {0}, cnt[N] = {0}, ans = 0; // LL防止爆intscanf("%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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/137872.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

深入理解CI/CD流程：改变你的开发生命周期

深入理解CI/CD流程：改变你的开发生命周期

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…
阅读更多...
SAP CRM 模块：概述，体系结构

SAP CRM 模块：概述，体系结构

前言 CRM 代表“客户关系管理”&#xff0c;是一组有助于以有组织的方式管理客户关系的方法和工具。 在当今竞争激烈的商业环境中&#xff0c;顶级公司的注意力越来越集中于其最有价值的资产– 客户。 因此&#xff0c;这些公司需要一种合适的软件解决方案来迎合其客户&#…
阅读更多...
Grafana设置默认主页

Grafana设置默认主页

点击【设置/管理】-> 【默认首选项 Preferences】-> 【主页仪表盘】 在下拉中选择一个页面作为主页即可
阅读更多...
软件设计模式系列之五——建造者模式

软件设计模式系列之五——建造者模式

1 模式的定义 建造者模式是一种对象创建型设计模式&#xff0c;它将一个复杂对象的构建过程与其表示分离。这意味着你可以使用相同的构建过程来创建不同类型的对象&#xff0c;而不必关心每个对象的内部细节。这种模式适用于构建具有复杂配置的对象&#xff0c;例如具有多个可…
阅读更多...
Java Gradle

Java Gradle

目录 1. Gradle简介 1.1 什么是Gradle 1.2 Gradle优点 1.2.1 自动化构建 1.2.2 Gradle相当于构建工具的进化版 1.2.3 对于Gradle优点&#xff0c;官网是这么说的 1.3 Grade 的版本说明 2. Groovy语言基础 2.1 基础语法 2.2 String 与 GString 2.2.1 String 2.2.2 插…
阅读更多...
将docker镜像打成tar包

将docker镜像打成tar包

# 打包 docker save -o zookeeper.tar bitnami/zookeeper:3.9.0-debian-11-r11# 解压 docker load -i zookeeper.tar
阅读更多...
使用@Builder注解后，该对象 拷贝时出现java.lang.InstantiationException异常报错

使用@Builder注解后，该对象 拷贝时出现java.lang.InstantiationException异常报错

报错信息&#xff1a; 2023-09-21T16:02:00.83308:00 ERROR 23220 --- [nio-8080-exec-1] i.global.iot.common.utils.ConvertUtils : convert error java.lang.InstantiationException: io.global.iot.common.modules.dto.ZyOrderDTOat java.base/java.lang.Class.newInsta…
阅读更多...
如何使用高压放大器驱动高容性负载

如何使用高压放大器驱动高容性负载

使用高压放大器驱动高容性负载是一个具有挑战性的任务&#xff0c;需要仔细考虑电路设计和操作技巧。下面西安安泰Aigtek将为您介绍一些关于如何使用高压放大器驱动高容性负载的方法和注意事项。 首先&#xff0c;让我们了解一下高容性负载。高容性负载通常指电容值较大的负载元…
阅读更多...
uniapp开发h5，解决项目启动时，Network: unavailable问题

uniapp开发h5，解决项目启动时，Network: unavailable问题

网上搜了很多&#xff0c;发现都说是要禁用掉电脑多余的网卡&#xff0c;这方法我试了没有好&#xff0c;不晓得为啥子&#xff0c;之后在网上看&#xff0c;uniapp的devServer vue2的话对标的就是webpack4的devserver&#xff08;除了复杂的函数配置项&#xff09;&#xff0c…
阅读更多...
抗锯齿的线

抗锯齿的线

抗锯齿的线 右下角的时候h是0,到顶部 h是1&#xff0c;然后中间y相距4个像素&#xff0c;那dy就是0.25 如果让h abs(fract(h - 0.5) - 0.5) 中间一行0.5&#xff0c;第一行 第三行都是0.25&#xff0c;两端都是0 根据插值来看 这里是 如果用h/dy 那么第一行以上&#xff0…
阅读更多...
【JavaEE】多线程案例-线程池

【JavaEE】多线程案例-线程池

文章目录 1. 什么是线程池2. 为什么要使用线程池&#xff08;线程池有什么优点&#xff09;3. 如何使用Java标准库提供的线程池3.1 创建一个线程池对象3.2 什么是工厂模式3.3 为什么要使用工厂模式3.4 Executors 创建不同具有不同特性的线程池3.5 ThreadPool 类的构造方法3.6 线…
阅读更多...
SOLIDWORKS2024新功能--SOLIDWORKS篇（二）

SOLIDWORKS2024新功能--SOLIDWORKS篇（二）

该章节包括以下主题&#xff1a; 切口工具槽口延伸戳记工具薄片和槽口中的切割法线 切口工具 您可以使用切口工具在空心或薄壁圆柱体和圆锥体中生成切口。通过选择圆柱面或圆锥面上的边线&#xff0c;您可以将零件平展为钣金。 在早期版本中&#xff0c;如果您有圆柱形或圆锥形…
阅读更多...
【java】【SpringBoot】【四】原理篇 bean、starter、核心原理

【java】【SpringBoot】【四】原理篇 bean、starter、核心原理

目录 一、自动配置 1、bean加载方式&#xff08;复习&#xff09; 1.1 加载方式-xml方式生命bean 1.2 加载方式-xml注解方式声明bean 1.3 注解方式声明配置类 1.4 FactoryBean 1.5 proxyBeanMethod属性 1.6 使用Import注解导入 1.7 使用上下文对象在容器初始化完毕后注…
阅读更多...
安防监控系统/视频云存储/视频监控平台EasyCVR无法级联上级平台，该如何解决？

安防监控系统/视频云存储/视频监控平台EasyCVR无法级联上级平台，该如何解决？

安防视频监控系统EasyCVR平台能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;TSINGSEE青犀视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频流&#xff0c;也…
阅读更多...
GIT使用需知，哪些操作会导致本地代码变动

GIT使用需知，哪些操作会导致本地代码变动

系列文章目录 手把手教你安装Git&#xff0c;萌新迈向专业的必备一步 GIT命令只会抄却不理解&#xff1f;看完原理才能事半功倍&#xff01; 常用GIT命令详解&#xff0c;手把手让你登堂入室 GIT实战篇&#xff0c;教你如何使用GIT可视化工具 GIT使用需知&#xff0c;哪些操作…
阅读更多...
二蛋赠书三期：《C#入门经典（第9版）》

二蛋赠书三期：《C#入门经典（第9版）》

文章目录 前言活动规则参与方式本期赠送书籍介绍作者介绍内容简介读者对象获奖名单 结语 前言 大家好&#xff01;我是二蛋&#xff0c;一个热爱技术、乐于分享的工程师。在过去的几年里&#xff0c;我一直通过各种渠道与大家分享技术知识和经验。我深知&#xff0c;每一位技术…
阅读更多...
做接口测试如何上次文件

做接口测试如何上次文件

【软件测试面试突击班】如何逼自己一周刷完软件测试八股文教程&#xff0c;刷完面试就稳了&#xff0c;你也可以当高薪软件测试工程师&#xff08;自动化测试&#xff09; 在日常工作中&#xff0c;经常有上传文件功能的测试场景&#xff0c;因此&#xff0c;本文介绍两种主流编…
阅读更多...
CrossOver 23 正式发布：可在 Mac 上运行部分 DX12 游戏

CrossOver 23 正式发布：可在 Mac 上运行部分 DX12 游戏

CodeWeivers 公司于今年 6 月发布了 CrossOver 23 测试版&#xff0c;重点添加了对 DirectX 12 支持&#xff0c;从而在 Mac 上更好地模拟运行 Windows 游戏。 该公司今天发布新闻稿&#xff0c;表示正式发布 CrossOver 23 稳定版&#xff0c;在诸多新增功能中&#xff0c;最值…
阅读更多...
netty之数据读写源码阅读

netty之数据读写源码阅读

数据读写 write 从client端的写开始看 client与服务端建立完connect后可以从future里拿到连接的channel对象。这里的channel是io.netty.channel.Channel对象。 调用其channel.writeAndFlush(msg);方法可以进行数据发送。 writeAndFlush会调用pipeline的writeAndFlush方法 …
阅读更多...
Nacos内核设计之一致性协议(上)

Nacos内核设计之一致性协议(上)

Nacos一致性协议 Nacos技术架构 先简单介绍下Nacos的技术架构 从而对nacos有一个整体的认识 如图Nacos架构分为四层 用户层、应用层、核心层、各种插件 再深入分析下nacos一致性协议的发展过程及原理实现 为什么nacos需要一致性协议 Nacos是一个需要存储数据的一个组件 为了实…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发