斯德哥尔摩 的博客

斯德哥尔摩 的博客

P3131 [USACO16JAN]子共七Subsequences Summing to Sevens

posted on 2018-10-21 20:40:56 | under 刷题 |

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;
}