Steven_MengのBlog

传送门

为什么你们的题解都写得这么长。

考虑前缀和,设$a[i]$的前缀和数组为$sum[i]$,则我们有$\sum _{i=x} ^y a[i]=sum[y]-sum[x-1]$,因为$\sum _{i=x} ^y a[i] \mod 7 = 0$,所以我们有$sum[y]-sum[x-1] \mod 7= 0$,即$sum[y]$和$sum[x-1]$模$7$同余。

考虑贪心,我们设$last[i]=\min { j , sum[j] \mod 7 = i}$,就可以求出模$7$意义下离现在位置$y$最远的$x$,满足$sum[x-1]$和$sum[y]$同余,就可以搞定了。

记得每步都%7,要不然可能会爆$\rm int$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define MAXN 500005
using namespace std;
int a[MAXN],last[7];
int main(){
int n;
scanf("%d",&n);
for (register int i=1;i<=n;++i) scanf("%d",&a[i]);
memset(last,0x3f,sizeof(last));
int ans=0;
for (register int i=1;i<=n;++i){
a[i]=(a[i]+a[i-1])%7;
ans=max(ans,i-last[a[i]]);
last[a[i]]=min(last[a[i]],i);
}
printf("%d\n",ans);
}

 评论