bzoj4511: [Usaco2016 Jan]Subsequences Summing to Sevens

时间:2022-03-22 10:41:16

前缀和.

设f[i]为前缀和%7=i的第一个点。那么答案就是max(i-f[s[i]%7])了。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 50000 + 10; int a[maxn],s[maxn];
int f[10],n,ans; int main() {
for(int i=1;i<7;i++) f[i]=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
s[i]=(s[i-1]+a[i])%7;
if(f[s[i]]==-1) f[s[i]]=i;
else {
ans=max(ans,i-f[s[i]]);
}
}
printf("%d\n",ans);
}