题解 P3131 【[USACO16JAN]子共七Subsequences Summing to Sevens】

「已注销」 · 2018-02-09 21:05:46 · 题解

前缀和，s[i]表示[1,i]的和，[l,r]的和就可以拆成s[r]-s[l-1]，当s[r]和s[l-1]模7相同时，区间就能被7整除，求出前缀和每个余数对应的最小的l-1和最大的r从而算出最长区间长度，可以边读入边记录。端点模7为0到6的最长区间长度的最大值就是答案，注意判断区间是否存在 用滚动数组，时间O(n)，空间常数

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a,s,l[]={0,-1,-1,-1,-1,-1,-1},r[7],ans; //s是前缀和，l[i]存%7为i的最小l-1,r[i]存%7为i的最大r,-1代表没有%7为i的前缀和,当有任意前缀和s[x]%7等于0时,最长区间长度就是x
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a);
        s=(s+a)%7;
        if(l[s]==-1)l[s]=i;
        r[s]=i;
    }
    for(int i=0;i<7;++i)if(l[i]!=-1)ans=max(ans,r[i]-l[i]);
    printf("%d",ans);
}