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

· · 题解

2021.7.30 update:

添加了 \LaTeX ，补充了被 hack 的问题。 （实在没想到4年前的代码会被hack)

（这题解审核也太严了，好辛苦啊>_<）

首先：

这个题肯定不能直接模拟，你要是暴力枚举端点，看看数据范围。。。。50000^3 下辈子都过不去。

然后：

我们就想到了一个求区间和的好东西：

当然是 “前缀和” 了啊！

我们只要先预处理前缀和，然后用 pre[r]-pre[l] 就是区间和了，这样只要再拿他 \bmod 7 就可以判断了，最后求最大长度就可以了！

发现不行。。。。 n^2 的复杂度啊。。。预计得分 70 。

改思路！

我们可以先直接求 \bmod 7 意义下的前缀和，然后只要看看余数的重复就可以了。

这里需要用到一个小定理：若两个数相减 (\bmod 7=0) ，那么这两个数 \bmod 7 的余数一定相同！！（很好证明，自己有兴趣不妨去试试证明）

这样的话瞬间就简单了。

我们只要求出相同的一个余数第一次和最后一次之间的长度即是最长长度！ 但是我们不知道哪个余数最长，所以：

枚举 0 ~ 6 共 7 个余数各自的最长长度，再在他们 7 个里找最长的！

最后附上代码（每步都有解释哦！）

 #include<bits/stdc++.h>
using namespace std;
const int maxn=50010;
int pre[maxn];
int n,len,mx=-1;
int first[7],last[7];//%7的余数为0~6,所以开7的数组就可以了； 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i];
        pre[i]=(pre[i]+pre[i-1])%7; //%7意义下的前缀和 ，就变成了前缀和%7的余数；      
    }
    for(int i=n;i>=1;i--)//(pre[i]是当位置为i时 前缀和%7的余数） 
        first[pre[i]]=i;   //第一次出现pre[i]这个余数的时候的位置为i ；
    //倒着扫一遍 不断更新最后就是这个余数第一次出现； 
    first[0]=0;//从头加到i是7的倍数的情况下，需要把0的第一次出现设为0，即把整个区间[1,i]选上了。
    for(int i=1;i<=n;i++)
        last[pre[i]]=i;//最后一次出现pre[i]这个余数时位置为i； 

    for(int i=0;i<=6;i++)   //这里是看哪个余数的长度最大，last[i]-first[i]就是余数i的最大长度
    //(最后一次出现减第一次出现 显然是最长的)
    //两个位置相减就是长度；因为是前缀和(前缀和为【i+1，j】的区间,所以j-i即为区间的长度） 
    //这里不是一般的 j-i+1(末位置 减 首位置+1） 为长度，紧扣前缀和的定义！！ 
    mx=max(last[i]-first[i],mx);
    //前缀和求原区间长度是 j-i；一般的区间长度是 j-i+1； 
    cout<<mx<<endl;
}