[蓝桥杯2017初赛]k倍区间 前缀和

题目描述

给定一个长度为N的数列,A1, A2, ... AN。

如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。

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

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)

以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)  

输出

输出一个整数,代表K倍区间的数目。
文章来源地址https://www.yii666.com/article/754242.html网址:yii666.com

样例输入

5 2
1
2
3
4
5

样例输出

6

题解:首先暴力判断一定会超时的,

如果区间[l,r]的和(sum[r]-sum[l])%k==0,那么sum[r]%k==sum[l]%k,

所以只要判断有几个前缀和%k的值相等,即可以判断几个区间和%k==0

用样例举个例子:

sum[1]%2==1       此时vis[1]==0,所以ans=ans+vis[1]=0     vis[1]=1

sum[2]%2==1  此时vis[1]==1,所以ans+ans+vis[1]=1     vis[1]=2

sum[3]%2==0  此时vis[0]==0,所以ans=ans+vis[0]=1           vis[0]=1文章来源地址:https://www.yii666.com/article/754242.html

sum[4]%2==0  此时vis[0]==1,所以ans=ans+vis[0]=2      vis[0]=2

sum[5]%2==1  此时vis[1]==2,所以ans=ans+vis[1]=4      vis[1]=3网址:yii666.com<

这个时候ans=4,这里统计的是区间(1,n]之间的子区间和%k==0的区间个数,还要加上[1,n]之间区间和%k==0的个数(以样例为例是区间[1,3]和[1,4])

所以ans=6

注意ans用long long文章地址https://www.yii666.com/article/754242.html

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<string.h>
#define ll long long
using namespace std;
int a[],sum[],vis[];
int main()
{
int n,k;
cin>>n>>k;
ll ans=;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
cin>>a[i];
sum[i]=(sum[i-]+a[i])%k;//如果区间[l,r]的和(sum[r]-sum[l])%k==0
ans=ans+vis[sum[i]]; //那么sum[r]%k==sum[l]%k
vis[sum[i]]++; //所以只要判断有几个前缀和%k的值相等,即可以判断几个区间和%k==0
}
cout<<ans+vis[]<<endl;
return ;
}
 

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png