网站建设 实施计划,外贸网站电子建设,交换友情链接的网站标准是什么,福州网站设计知名乐云seo前缀求和算法是什么
前缀和算法就是以空间去换取时间#xff0c;可用于快速求数组的区间和#xff0c;它可以用于一维数组和二维数组#xff0c;但我现在只接触了一维数组并没有接触二维数组#xff0c;所以在这里先介绍一维数组前缀和相关的知识
前缀和典型代码 for(int…前缀求和算法是什么
前缀和算法就是以空间去换取时间可用于快速求数组的区间和它可以用于一维数组和二维数组但我现在只接触了一维数组并没有接触二维数组所以在这里先介绍一维数组前缀和相关的知识
前缀和典型代码 for(int i1;in;i){scanf(%d,t);s[i]s[i-1]t;}
这里一定要求i从1开始计数当然在这里我们统一的将下表设置为从1开始具体是要考虑到我们的边界问题也就是S[1]的求法问题为了保证我们循环的统一性我们要将S[0]设置为0所以我们索性就将下标从1开始设置起这样也有利于我们后面的初始化同时也方便了我们的计算
题例
以题为例见真章
P8649 [蓝桥杯 2017 省 B] k 倍区间
题目链接[蓝桥杯 2017 省 B] k 倍区间 - 洛谷
题目描述
给定一个长度为 NN 的数列A1,A2,⋯ANA1,A2,⋯AN如果其中一段连续的子序列 Ai,Ai1,⋯Aj(i≤j)Ai,Ai1,⋯Aj(i≤j) 之和是 KK 的倍数我们就称这个区间 [i,j][i,j] 是 KK 倍区间。
你能求出数列中总共有多少个 KK 倍区间吗
输入格式
第一行包含两个整数 NN 和 KK(1≤N,K≤105)(1≤N,K≤105)。
以下 NN 行每行包含一个整数 AiAi(1≤Ai≤105)(1≤Ai≤105)。
输出格式
输出一个整数代表 KK 倍区间的数目。
代码
#includeiostream
using namespace std;
long long a[100005],b[100005],n,k,c,t;
int main()
{cinnk;for(int i1;in;i){cint;a[i]a[i-1]t;}for(int i0;in;i){cb[a[i]%k];}coutc;return 0;
}
这里解释一下这道题目以及代码
题目的题意就是获取这n个数的连续区间之后是不是k的倍数
代码解释首先去求前缀和这是第一个for循环需要做的
第二个for循环要做的就是求区间我当时有个疑问就是为什么这样去求区间在这里解释一下当两个数去余同一个数并且余数相同那么这两个数之差就是这个数的倍数如9和17余8都为1他们相减就是8是8的倍数这里还需要注意他这里是先把b[a[i]%k]的值先赋给c之后在自加的所以当两个数的余数相同时只会加一个1还有注意这个i必需从0开始因为有的数余数肯定为0那么这个数就可以是一个区间就要相加
这道题有第二种解法但感觉太麻烦我们直接去求这几个和的差那么第二个就需要两个for循环增加了时间复杂度
第二种方法代码如下
#includeiostream
using namespace std;
long long a[100005],b[100005],n,k,c,t;
int main()
{cinnk;for(int i1;in;i){cint;a[i]a[i-1]t;}for(int i0;in;i){for(int ji1;jn;j){if((a[j]-a[i])%k0)c;}}coutc;return 0;
}
交上去被提示时间超时了所以第二种方法时间复杂度太大了
