【前缀和】截断数组、K倍区间、激光炸弹

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

题目:截断数组

白话讲解:

题解:

代码实现:

题目:激光炸弹

白话讲解:

题解:

代码实现:

题目:k倍区间

题目描述

输入描述

输出描述

输入输出样例

白话讲解:

题解:

代码实现:

完结撒花：

---

题目:截断数组

给定一个长度为 n 的数组 a1,a2,…,an

现在，要将该数组从中间截断，得到三个非空子数组。

要求，三个子数组内各元素之和都相等。

请问，共有多少种不同的截断方法？

输入格式

第一行包含整数 n。

第二行包含 n个整数 a1,a2,…,an

输出格式

输出一个整数，表示截断方法数量。

数据范围

前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤1e5，−10000≤ai≤10000。

输入样例1：

4
1 2 3 3

输出样例1：

1

输入样例2：

5
1 2 3 4 5

输出样例2：

0

输入样例3：

2
0 0

输出样例3：

0

白话讲解:

将一个数组中个元素之和三等分，有几种分法

题解:

通过题目所给提示，这题很容易想到用前缀和来处理。

三个非空数组，意味着可以讲三个数组分为两个部分，末端位置到n为一个区间，大小为元素总和的三分之一，0-n-1为元素总和的三分之二。

先判断元素总和是否能被三整除若不能被三整除则无法分成三个区间和，直接输出0即可

之后遍历前缀和数组，若一个区间为大小为三分之一，则记录下来cnt，之后若这个区间后的一个点的大小为三分之二，则说明整个数组被三等分了，则加上前面三等分点的个数。

代码实现:

#include<iostream>
using namespace std;
const int N=100010;
int s[N];
int n=0;
int ans=0;
typedef long long ll ;
ll res;
int main()
{cin>>n;s[0]=0;int x=0;for(int i=1;i<=n;i++){cin>>x;s[i]=s[i-1]+x;}if(s[n]%3)cout<<0;else{ll res=0,cnt=0;for(int j=2;j<n;j++){if(s[j-1]==s[n]/3)cnt++;if(s[j]==s[n]/3*2)res+=cnt;}printf("%lld",res);}return 0;
}

题目:激光炸弹

地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 R×R个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。

接下来 N行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi，分别代表目标的 x坐标，y坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

0≤R≤1e9
0<N≤100000,
0≤Xi,Yi≤5000
0≤Wi≤1000

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

白话讲解:

在地图上若干个点放置在财物，之后给你一个炸弹，爆炸范围为R*R的一个正方形，也就是说能框住R*R内的所有财物，如何放置炸弹，损毁的财物价值最大

题解:

一个典型的二维前缀和的问题，讲所有财物的价值存入对应的点，之后进行二位前缀和的处理即可。

注意 虽然R的范围是1e9，但是财物的范围仅为5000，所以我们R的范围只需要比5000大一点即将所有财物包括。

另外，这里受限于内存，最好将元素数组与前缀和数组一起存储，即用一个数组来处理前缀和的关系。

一些优化的做法，若我们前缀和处理的时候直接枚举5000大小的地图，会导致时间效率太低，虽然也能过，但是最好拓展下自己的思维，行列当中不需要枚举5000，枚举到，x，y出现的最大大小就可以了，之后就是处理二位前缀和，不会的话可以看看之前的博客 前缀和

代码实现:

#include <algorithm>
#include<iostream>
using namespace std;
const int N=5010;
int s[N][N]={0};
int main()
{int cnt,r,n,m;int x=0,y=0,w=0;cin>>cnt>>r;r=min(5001,r);n=m=r;while(cnt--){cin>>x>>y>>w;x++,y++;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][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];}}int  res=0;for(int i=r;i<=n;i++){for(int j=r;j<=m;j++){res=max(res,s[i][j]+s[i-r][j-r]-s[i-r][j]-s[i][j-r]);}}cout<<res;
}

题目:k倍区间

题目描述

给定一个长度为 N 的数列A1​,A2​,⋯AN​，如果其中一段连续的子序列Ai​,Ai​+1,⋯Aj​ ( �≤�i≤j ) 之和是 K 的倍数，我们就称这个区间[i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入描述

第一行包含两个整数 N 和 K(1≤N,K≤1e5 )。

以下 N 行每行包含一个整数Ai​ ( 1≤Ai​≤1e5 )

输出描述

输出一个整数，代表 K 倍区间的数目。

输入输出样例

示例

输入

5 2
1
2
3
4
5

输出

6

白话讲解:

找出长度区间内元素和为k的倍数，并统计这样的区间有几个。

题解:

长度区间内的元素，我们很容易就想到用前缀和的方式来处理。所以我们试试用暴力做法怎么去做

进行两层循环（类似双指针）右指针固定区间长度，左指针来遍历这个区间内前缀和，最后判断是否为k的倍数。

某一个区间长度的元素大小s[R]-s[L-1]为R到L的区间内元素的总和。我们要找到是(s[R]-s[L-1])%k=0.等式变换下就成为了 s[R]%k=s[L-1]%k 这时候要做的就变成去找s[L-1]%k何时与s[R]%k相等

我们可以拿一个数组来记录一下s[R]%k相同余数出现的个数 即cnt[s[R]%k]

当res+=该余数出现的次数。这里实现的效果其实为：第一次不会相加。只有第二次才会加上一，第三次加上二.......

另外需要初始化一下cnt[0]=1;

我是这样理解的，假设k=3，你的原始数组为 1 2 3 4 5 此时当i=2时s[2]=3 已经满足了k倍区间，但是因为第一次出现，所以不记录的原则，是不会被计算的。所以就导致答案少了一个。 

代码实现:

#include<iostream>
using namespace std;
const int N=100010;
typedef long long ll;
ll s[N],cnt[N];
int main()
{int n=0,k=0;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&s[i]);s[i]+=s[i-1];}ll res=0;cnt[0]=1;for(int i=1;i<=n;i++){res+=cnt[s[i]%k];cnt[s[i]%k]++;}printf("%lld\n",res);return 0;
}

完结撒花：

🌈本篇博客的内容【】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！