被普及-卡的没思路真是蒟蒻啊233
优化思路
每次都在枚举(a[r]-a[l-1])%7==0,所以可以认为数组大小对最终答案没有影响,考虑对前缀和数组取模,那么如果有a[r]的值等于a[l-1]的值相等(即余数相等),那么两者相减余数为0,则为7的倍数。
Debug
因为是对前缀和数组取模,那么a[r]-a[l]就是原数组的长度,不用+1,但是仔细一看会发现枚举的时候第一个数永远没有算在内,即包含第一个数的连续区间,那么初始化的时候判断一下就行了。
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;int n,a[N],l[7],r[7],ans;signed main(){cin>>n;for(int i=1;i<=n;++i){cin>>a[i];a[i]+=a[i-1];a[i]%=7;if(!a[i])ans=i;//累计算上1的区间if(!l[a[i]])l[a[i]]=i;r[a[i]]=i;}for(int i=0;i<7;++i)ans=max(ans,r[i]-l[i]);cout<<ans<<endl;return 0;
}