【算法Camp】【每日一题】Namomo Spring Camp Div1 第2 周 第 1 题 摘桃子

题目：

桃园里面有 n 个人在摘桃子。现在 n 个人排成一排，从左到右每个人拥有的桃子数是 ai。 桃园里有一个免费获得桃子的规则，如果连续 x 个人的桃子总数除以 k 的余数正好是 x, 那么这 x 个人就可以免费获得桃子,并且每天只有一次免费获得桃子的机会。 请聪明的你算出一共有多少种不同的方案可以使今天有人免费获得桃子。

输入格式

第一行两个数字 n 、k。

接下来一行 n 个整数 a1,a2,…,an。

输出格式

一个数，表示答案。

样例输入

8 44 2 4 2 4 2 4 2

样例输出

7

NOTE

七个不同方案分别是: a1,a2 、 a2,a3 、a3,a4 、a4,a5 、 a5,a6 、a6,a7 、a7,a8。 注：只要子串有一个边界不同即为不同的方案

数据规模

所有数据保证 1≤n≤2×105,1≤k≤109,1≤ai≤109。

题解：首先处理出a的前缀和s，那么要满足某一个连续的子段的和模k为他自己的长度，即为：(s[r]-s[l-1])%kr-l+1,移项后即为：(s[r]-r)%k(s[l-1]-(l-1))%k那么首先这段的长度就不能超过k，所以可以用滑动窗口来做这道题目，窗口大小为k-1，每次右移后加入的数字为map[(s[x-1]-(x-1))%k]++，当前r的答案即为map[(s[i]-i)%k];

代码：

#include<iostream>#include<algorithm>#include<cstring>#include<map>using namespace std;typedef long long LL;const int N=200010;LL a[N],sum[N];map<int,int>li;int main(){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum[i]+=sum[i-1]+a[i];int l=1,r=0;LL res=0;for(int i=1;i<=n;i++){r++;li[(sum[r-1]-r+1)%k]++;if(r-l+1>=k){li[(sum[l-1]-l+1)%k]--;l++;}res+=li[(sum[r]-r)%k];}printf("%lld\n",res);}

如果觉得《【算法Camp】【每日一题】Namomo Spring Camp Div1 第2 周 第 1 题 摘桃子》对你有帮助，请点赞、收藏，并留下你的观点哦！