洛谷P3131题解【前缀和】【同余】

P3131 [USACO16JAN] Subsequences Summing to Sevens S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目分析

一看到这题，先想到的是用前缀和，于是写出了以下代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> a(n),res(n);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        res[i]=res[i-1]+a[i];
    }
    for(int i=n;i>=1;--i){ //让i表示区间长度
        for(int j=n;j-i+1>=1;--j){
            if((res[j]-res[j-i])%7==0){
                cout<<i;
                return 0;
            }
        }
    }
    cout<<0;
    return 0;
}  

结果是又有RE又有WA，还有TLE。再一看，忘记开 long long了，稍微改了一下，加了快读，依然RE和TLE。再一想，其实不用保存原数据，只要保存前缀和就行，但是这依然解决不了TLE的问题。看来是有些地方没想到了。学习了一下题解之后，我才知道还可以用同余的定义来优化。

给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。（百度百科）

也就是说，我们只要找到两个对7同余的前缀和，使得该区间的长度（即两个前缀和序号之差）尽可能大，最后再从各个余数的情况中找到最大的即可。需要注意的是，当讨论余数为0的情况时，我们只需要找到满足条件的序号尽可能大的前缀和即可。（笔者数学较差，表述可能不太清楚，见谅。）

AC代码：

#include <bits/stdc++.h>
using namespace std;
long long res[50002];
int l[7],r[7];
inline long long read(){
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main(){
	int n=read();
    for(int i=1;i<=n;++i){
        res[i]=read();
        res[i]+=res[i-1];
        int tmp=res[i]%7;
        if(i>r[tmp]) r[tmp]=i;
        if(l[tmp]==0) l[tmp]=i;
        else if(i<l[tmp]) l[tmp]=i;   
    }
    int mx=0;
    if(r[0]) mx=r[0];//不用看左边
    for(int i=1;i<7;++i){
        if(r[i]-l[i]>mx&&l[i]!=0){
            mx=r[i]-l[i];//千万不要+1，因为这是前缀和而不是原数列
            //printf("i:%d mx:%d r:%d l:%d \n",i,mx,r[i],l[i]);
        }
    }
    printf("%d",mx);
	return 0;
}