雁塔网站建设,广东汇鑫科技网站建设,亳州蒙城网站建设,域名备案网站建设方案Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … 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之后若这个区间后的一个点的大小为三分之二则说明整个数组被三等分了则加上前面三等分点的个数。
代码实现:
#includeiostream
using namespace std;
const int N100010;
int s[N];
int n0;
int ans0;
typedef long long ll ;
ll res;
int main()
{cinn;s[0]0;int x0;for(int i1;in;i){cinx;s[i]s[i-1]x;}if(s[n]%3)cout0;else{ll res0,cnt0;for(int j2;jn;j){if(s[j-1]s[n]/3)cnt;if(s[j]s[n]/3*2)rescnt;}printf(%lld,res);}return 0;
} 题目:激光炸弹 地图上有 N 个目标用整数 Xi,Yi 表示目标在地图上的位置每个目标都有一个价值 Wi。 注意不同目标可能在同一位置。 现在有一种新型的激光炸弹可以摧毁一个包含 R×R个位置的正方形内的所有目标。 激光炸弹的投放是通过卫星定位的但其有一个缺点就是其爆炸范围即那个正方形的边必须和 xy轴平行。 求一颗炸弹最多能炸掉地图上总价值为多少的目标。 输入格式 第一行输入正整数 N 和 R分别代表地图上的目标数目和正方形包含的横纵位置数量数据用空格隔开。 接下来 N行每行输入一组数据每组数据包括三个整数 Xi,Yi,Wi分别代表目标的 x坐标y坐标和价值数据用空格隔开。 输出格式 输出一个正整数代表一颗炸弹最多能炸掉地图上目标的总价值数目。 数据范围 0≤R≤1e9 0N≤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枚举到xy出现的最大大小就可以了之后就是处理二位前缀和不会的话可以看看之前的博客 前缀和
代码实现:
#include algorithm
#includeiostream
using namespace std;
const int N5010;
int s[N][N]{0};
int main()
{int cnt,r,n,m;int x0,y0,w0;cincntr;rmin(5001,r);nmr;while(cnt--){cinxyw;x,y;nmax(n,x);mmax(m,y);s[x][y]w;}for(int i1;in;i){for(int j1;jm;j){s[i][j]s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1];}}int res0;for(int ir;in;i){for(int jr;jm;j){resmax(res,s[i][j]s[i-r][j-r]-s[i-r][j]-s[i][j-r]);}}coutres;
} 题目:k倍区间 题目描述 给定一个长度为 N 的数列A1,A2,⋯AN如果其中一段连续的子序列Ai,Ai1,⋯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])%k0.等式变换下就成为了 s[R]%ks[L-1]%k 这时候要做的就变成去找s[L-1]%k何时与s[R]%k相等
我们可以拿一个数组来记录一下s[R]%k相同余数出现的个数 即cnt[s[R]%k]
当res该余数出现的次数。这里实现的效果其实为第一次不会相加。只有第二次才会加上一第三次加上二.......
另外需要初始化一下cnt[0]1;
我是这样理解的假设k3你的原始数组为 1 2 3 4 5 此时当i2时s[2]3 已经满足了k倍区间但是因为第一次出现所以不记录的原则是不会被计算的。所以就导致答案少了一个。
代码实现:
#includeiostream
using namespace std;
const int N100010;
typedef long long ll;
ll s[N],cnt[N];
int main()
{int n0,k0;scanf(%d%d,n,k);for(int i1;in;i){scanf(%lld,s[i]);s[i]s[i-1];}ll res0;cnt[0]1;for(int i1;in;i){rescnt[s[i]%k];cnt[s[i]%k];}printf(%lld\n,res);return 0;
}完结撒花 本篇博客的内容【】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
