一维与二维前缀和(蓝桥杯复习+例题讲解+模板c++)

article/2024/6/24 18:26:38

文章目录

    • 前缀和
    • 二维前缀和
    • 总结
    • 3956. 截断数组
    • 99. 激光炸弹

文章首发于: My Blog 欢迎大佬们前来逛逛

前缀和

前缀和是一种常见的算法,用于快速计算数组中某一段区间的和。前缀和的思想就是预处理出数组中前缀和,然后用后缀和减去前缀和,即可快速计算区间和。

以一维数组为例,设 aia_iai 表示数组中第 iii 个元素的值,sumisum_isumi 表示数组中前 iii 个元素的和,即: sumi=∑j=1iajsum_i = \sum_{j=1}^{i} a_jsumi=j=1iaj 则对于区间 [l,r][l, r][l,r] 的和可以表示为: ∑i=lrai=sumr−suml−1\sum_{i=l}^{r} a_i = sum_r - sum_{l-1}i=lrai=sumrsuml1 这里需要注意的是,我们需要在原数组的前面插入一个值为 000 的元素,这样才能计算出 sum0sum_0sum0,也就是前 000 个元素的和。 以下是一维前缀和的代码实现:

vector<int> a; // 原数组
vector<int> sum(a.size() + 1, 0); // 前缀和数组
// 计算前缀和
for (int i = 1; i <= a.size(); i++) {sum[i] = sum[i-1] + a[i-1];
}
// 计算区间和
int l = 3, r = 7;
int ans = sum[r] - sum[l-1]; //[3,7]的区间和

二维前缀和

对于二维数组,我们可以先对每一行进行一维前缀和,然后对每一列进行一维前缀和,即可得到二维前缀和数组。 设 ai,ja_{i,j}ai,j 表示二维数组中第 iii 行第 jjj 列的元素值,sumi,jsum_{i,j}sumi,j 表示以 (i,j)(i,j)(i,j) 为右下角的矩阵的元素和,则有: sumi,j=∑k=1i∑l=1jak,lsum_{i,j} = \sum_{k=1}^{i} \sum_{l=1}^{j} a_{k,l}sumi,j=k=1il=1jak,l 则对于矩阵 [x1,y1,x2,y2][x1,y1,x2,y2][x1,y1,x2,y2] 的元素和可以表示为: ∑i=x1x2∑j=y1y2ai,j=sumx2,y2−sumx1−1,y2−sumx2,y1−1+sumx1−1,y1−1\sum_{i=x1}^{x2}\sum_{j=y1}^{y2} a_{i,j} = sum_{x2,y2} - sum_{x1-1,y2} - sum_{x2,y1-1} + sum_{x1-1,y1-1}i=x1x2j=y1y2ai,j=sumx2,y2sumx11,y2sumx2,y11+sumx11,y11 以下是二维前缀和的代码实现:

vector<vector<int>> a; // 原数组
vector<vector<int>> sum(a.size() + 1, vector<int>(a[0].size() + 1, 0)); // 二维前缀和数组
//前缀和的预处理
for (int i=1;i<=a.size();i++){for (int j=1;j<=a[0].size();j++){sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];}
}
// 计算矩阵的元素和
int x1 = 2, y1 = 3, x2 = 5, y2 = 7;
int ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];

总结

前缀和是一种非常实用的算法,可以用于快速计算数组中某一段区间的和。在一维数组中,只需要预处理出前缀和数组即可;在二维数组中,需要先对每一行进行一维前缀和,然后再对每一列进行一维前缀和,得到二维前缀和数组。

3956. 截断数组

3956. 截断数组

题目要求:把一个数组从中间分开两份,使得这个数组被分成三份,其中每一份都是非空的,而且要求每一份的元素的和都相等。

例:

4
1 2 3 3

从下标为2的地方分第一份,下标为3的地方分第二份,因此可以分成如下的三段序列:

1 2,  3 ,  3

其中每一段的和都是相等的,为3。

每一段必须是非空的,如果:

2
0 0

则无解,因为这个序列无法分成三份,因此输出 0

同理,如果分不出三份,使得每一份的和都相等,则也输出0

我们需要得到的是分割的方案数。


一维前缀和的思想:我们统计这个序列的前缀和,以 1 2 3 3为例:

原数组为 nums[4]={1,2,3,3} ;前缀和数组为:presum[4]={1,3,6,9}

因此我们可以发现:如果数组的总和不能被3整除,则它一定不能分成三份,此时直接输出0即可。

如果数组的总和能够被3整除,则还不一定存在方案,例如:3 3,但是它只有两份。

我们可以得出另一个结论,如果数组总和能够被3整除,并且还必须需要分成三份。

因此我们可以计算出 avg=总和的三分之一,则我们必须满足两个临界点:

  1. 找到一个满足 avg*2 的地方,如果找到了这个地方为i, 则后面 i到n 的和一定是avg。
  2. 找到一个满足 avg 的地方,如果找到了这个地方,则我们统计满足这个地方的方案数。

最后如果在 avg*2 的地方加上 avg*1 的方案数,则就是整个数组分成三份的合法方案数,因为后面的avg*3的地方就是整个数组的和,找到了这两个地方就可以确定整个数组一定是合法的。


#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N=1e5+10;
int nums[N],presum[N];
int n;
signed main(){cin>>n;int sum=0;for (int i=1;i<=n;i++){cin>>nums[i];presum[i]=nums[i]+presum[i-1];sum+=nums[i];}if (sum%3!=0){//一定不能分成三份cout<<0;}else{int avg=sum/3;int js=0;int ans=0;for (int i=1;i<n;i++){//一定要留给第三份一个元素的空间,所以不能取到nif (presum[i]==avg*2){ans+=js;}if (presum[i]==avg){++js;}}cout<<ans<<endl;}return 0;
}

99. 激光炸弹

99. 激光炸弹 - AcWing题库

题目要求:给你一个矩形区域,这个矩形区域上有几个点,每个点都具有一个值,并且给你一个R,使你在这个矩阵中所有的R*R的正方形中找到具有的值最大的一个正方形的总价值。

这道题就是二维前缀和的应用。

假设我的初始矩阵区域如图所示:

1 0
0 1

则转换为二维前缀和矩阵:

1 1
1 2

如果此时R为1,则表面上我们可以取得 2为最大值,但是其实我们的二维前缀和应该这样计算:

val=sum[i][j]-sum[i-1][j]-sum[i][j-1]+sum[i][j]

val=2-1-1+1=1,则答案为1,根据原二维数组我们也可知,答案为1


因此我们只需要预处理出二维数组的前缀和即可,然后根据所给的R,找到一个最大的区域,使得值最大,统计最大值即可。

需要注意的几个地方:

  1. 可能会出现相同的位置具有多个值,则把他们的值相加即可
  2. 由于没有告诉这个矩形范围是多大,因此每次我们直接枚举到题目要求的极大值即可,即5e3左右
  3. 从可以容纳的最小的 R*R的正方形范围开始,统计每一个R*R的值,然后统计最大值。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5010;
int nums[N+10][N+10];
int n,r;
int main(){cin>>n>>r;//r可能会出现一个大值:1e9,但是只需要到N即可r=min(r,N);for (int i=1;i<=n;i++){int x,y,w;cin>>x>>y>>w;nums[x+1][y+1]+=w;//可能出现相同的位置,值相加}//预处理前缀和for (int i=1;i<=N;i++){for (int j=1;j<=N;j++){nums[i][j]+=nums[i-1][j]+nums[i][j-1]-nums[i-1][j-1];}}//求出每一个R*R的正方形做具有的最大值int ans=0;for (int i=r;i<=N;i++){for (int j=r;j<=N;j++){ans=max(ans,nums[i][j]-nums[i-r][j]-nums[i][j-r]+nums[i-r][j-r]);}}cout<<ans;return 0;
}

http://www.ngui.cc/article/show-1007718.html

相关文章

【零基础入门SpringBoot2】—— Web开发_3

一、Web原生组件注入 如何向SpringBoot中注入Web的原生组件&#xff1f; 1、使用Servlet API &#xff08;1&#xff09;Servlet原生组件 创建一个Servlet类&#xff0c;让它继承原生的Servlet的实现类 HttpServlet &#xff0c;使用WebServlet注解指定我们的请求&#xff0c;…

MobaXterm 链接Linux Ubuntu

MobaXterm 链接Linux Ubuntu 1.查看是否安装 openssh-server sudo apt-get install open-server2.开启ssh服务 sudo /etc/init.d/ssh start3.查看虚拟机的IP ifconfig5.打开MobaXterm 将ip输入即可 如果传输文件&#xff0c;选择SFTP&#xff0c;步骤和上面一样

c++加解密算法总结

不可逆加密 概述 单向加密&#xff0c;主要是对明文的保密和摘要提取。算法包括MD5、SHA、HMAC等。 特点 压缩性&#xff1a;任意长度的数据&#xff0c;单向加密后长度都是固定的&#xff1b;抗修改性&#xff1a;对原数据进行任何改动&#xff0c;哪怕只修改1个字节&…

JAVA Session会话 Thymeleaf - 视图模板技术配置步骤

JAVAWebSession会话会话跟踪技术session保存作用域Thymeleaf - 视图模板技术配置过程Session会话 HTTP是无状态的&#xff1a;服务器无法区分这两个请求是同一个客户端发过来的&#xff0c;还是不同的客户端发过来的 现实问题&#xff1a;第一次请求是添加商品到购物车&#x…

model.train()、model.eval()什么时候用

model.train() 在使用 pytorch 构建神经网络的时候&#xff0c;训练过程中会在程序上方添加一句model.train()&#xff0c;作用是 启用 batch normalization 和 dropout 。 如果模型中有BN层&#xff08;Batch Normalization&#xff09;和 Dropout &#xff0c;需要在训练时…

Mac M1/Intel 芯片 Nginx+PHP开发环境配置——初探(一)

最近因为新买Mac M系列芯片笔记本&#xff0c;一直也没搭建过PHP的开发环境&#xff0c;花了一点时间特意在本机做了一次环境搭建测试具体如下。开始之前&#xff0c;需要安装一些工具来完成配置&#xff0c;工具列表如下:XcodeVS CodeHomebrewOpenSSL & wgetMySQLPostgres…

Spring《二》bean的实例化与生命周期

&#x1f34e;道阻且长&#xff0c;行则将至。&#x1f353; 目录一、bean实例化&#x1f34d;1.构造方法 ***2.静态工厂 *使用工厂创建对象实例化bean3.实例工厂 ***使用示例工厂创建对象实例工厂实例化beanFactoryBean二、生命周期&#x1f351;1.生命周期设置2.在main方法使…

Vector - CAPL - 实时时间on *

前面有简单的提到过on message的用法&#xff0c;但是对于整个on *家族来说&#xff0c;on message仅仅这是其中之一&#xff0c;为了能够的了解、学习这个家族的成员&#xff0c;因此做了专门的整理的&#xff0c;将囊括CALP用常用的所有的on *家族成员&#xff0c;并对其进行…

【JavaEE】Java设计模式-单例模式(饿汉式与懒汉式)

目录 1.设计模式是啥&#xff1f; 2.单例模式 2.1什么是单例模式 2.2饿汉模式 2.3懒汉模式 3.懒汉模式与饿汉模式的区别 1.设计模式是啥&#xff1f; 设计模式是前人经过总结&#xff0c;通过对不同应用场景应该运用何种方法解决问题的模式。我们可以将它看成NBA中的…

English Learning - L2-10 英音地道语音语调 鼻辅音 [m] [n] [ŋ] 舌边音 [l] [r] 2023.03.23 周四

English Learning - L2-10 英音地道语音语调 鼻辅音 [m] [n] [ŋ] 舌边音 [l] [r] 2023.03.23 周四课前准备活动和回顾鼻辅音鼻辅音 [m]鼻辅音 [n]鼻辅音 [ŋ]鼻辅音对比鼻辅音发音技巧对应单词对应的句子舌边音舌边音 [l]发音技巧对应单词[l] 和 [n] 的区分舌边音 [r]发音技巧…