P3131 [USACO16JAN]子共七Subsequences Summing to Sevens

· · 个人记录

P3131 [USACO16JAN]子共七Subsequences Summing to Sevens

首先前缀和没的说。

然后有个定理：

设seven[i]表示前缀和模7的值，若存在i<=j且seven[j]==seven[i]，则区间(i,j]的和为7的倍数。

于是我们可以O(n)扫出seven[i]==j,j\in[0,6]第一次出现的位置begin[j]和最后一次出现的位置end[j]。

然后答案为\max\{end[j]-begin[j]+1|j\in[0,6]\}。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 50010
using namespace std;
int n,ans=0;
int start[7],end[7];
long long sum[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
void work(){
    for(int i=0;i<=6;i++)ans=max(ans,end[i]-start[i]);
    printf("%d\n",ans);
}
void init(){
    n=read();
    sum[0]=0;
    for(int i=1;i<=n;i++){
        int x=read();
        sum[i]=sum[i-1]+x;
        if(!start[sum[i]%7])start[sum[i]%7]=i;
        end[sum[i]%7]=i;
    }
}
int main(){
    init();
    work();
    return 0;
}