品牌网站建设市场,深圳网站建设q.479185700惠,seo关键词怎么选,门户网站 源码[蓝桥杯 2017 省 B] k 倍区间
题目描述
给定一个长度为 N 的数列#xff0c;,,⋯#xff0c;如果其中一段连续的子序列 ,,⋯ (i≤j) 之和是 K 的倍数#xff0c;我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗#xff1f;
输入格式 … [蓝桥杯 2017 省 B] k 倍区间
题目描述
给定一个长度为 N 的数列,,⋯如果其中一段连续的子序列 ,,⋯ (i≤j) 之和是 K 的倍数我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗
输入格式
第一行包含两个整数 N 和 K(1≤N,K≤)。
以下 N 行每行包含一个整数 (1≤≤)。
输出格式
输出一个整数代表 K 倍区间的数目。
输入输出样例
输入 #1
5 2
1
2
3
4
5
输出 #1 6
说明/提示
时限 2 秒, 256M。蓝桥杯 2017 年第八届 对于这个题先用了暴力枚举来解题发现只能过两个样例其他的都超时了之后看了题解他们用了前缀和思想下面我就整理前缀和相关概念和解题方法。 前缀和
前缀和是什么
通俗理解前缀和就是任意一个元素前面所有元素的和包括本身
例如这有一个数组arr[3]{1,2,3} 如果设定一个数组为此数组的前缀和数组perfix[3]{1,3,6}
前缀和的好处
好处就是减少时间复杂度例如上面的题要求一段区间的和用暴力枚举就会超时。使用前缀和我们只需要用末尾的前缀和减去初位置的前缀和就可以得到该区间的和了
我们来举个例子吧。定义一个arr[6]{1,2,3,4,5,6}求这个数组的任意一个区间[i,j]的和
暴力枚举
我们肯定会从第一个元素开始每次往后1然后从第二个元素开始每次往后1...;
假设要求[i,j]这个区间的和 for(int t0;it;t)int num1arr[t];for(int mj;mj;m)int num2arr[m];int numnum2-num1;
前缀和
定义一个 前缀和数组从头开始求前缀和之后的前缀和就是前一个前缀和加上当前元素
prefix[0]arr[0];
for(int n0;narr.size;i)prefix[n]prefix[n-1]arr[n];
int numpredix[j]-prefix[i-1];prefix[j]-prefix[i-1]arr[i]arr[i1]...arr[j]; 因为这个题是一维的我们就先介绍一维前缀和。
K倍区间解题思路
这个题不仅利用了前缀和还要转换思想要求K的倍数也就是是说根据前缀和里面的元素的运算得到的结果只要没有余数就行为防止数值溢出我们可以只给前缀和里面存余数就行余数如果为0那么就是k的倍数。
因此这个前缀和数组中存的不是和而是和的余数。具体操作如下
prefix[0]arr[0];
for(int n0;narr.size;i)prefix[n](prefix[n-1]arr[n])/K;
第一步可以直接判断prefix数组里面的值是否0,等于0就是K 的倍数。
第二步就是中间子序列的值是否是K的倍数令这个子序列的左下标为left,令右下标为right那么子序列的和可以表示为prefix[right]-prefix[left-1],判断是不是K的倍数就是判断这个子序列的和除于K的余数是否为0。 prefix[right]-prefix[left-1])%K0 prefix[right]%K-prefix[left-1]%K0 prefix[right]%Kprefix[left-1]%K 因此只要判断prefix[right]%Kprefix[left-1]%K就行换个说法就是要找相同的有几个假如有a个相同这些相同的两两组合就可以构成一个子序列也就是高中学的排列组合我定义一个cnt数组里面的数就代表i向同的有几个然后两两组合也就是 最后不要忘了前缀和里面单独余数为0的也是K的倍数cnt[0]就是余数为0的个数。加上就行。
最后就是注意记得数据类型定义为long long int
具体代码如下 #includeiostream
#includevector
using namespace std;
long long int n1e610;
int main()
{long long int N,K,num0,i;cinNK;vector long long intarr(n);//原数组 vector intprefix(n);//前缀和数组vector long long intcnt(n);for(i1;iN;i){cinarr[i];//数组输入prefix[i](prefix[i-1]arr[i])%K;//前缀和数组 cnt[prefix[i]];//统计里面相同的 }for(i0;iN;i){numcnt[i]*(cnt[i]-1)/2;//将相同的进行排列组合 }coutnumcnt[0];//余数为0的本来就是K的倍数 return 0;}
