题目描述
Farmer John's NN cows are standing in a row, as they have a tendency to do from time to time. Each cow is labeled with a distinct integer ID number so FJ can tell them apart. FJ would like to take a photo of a contiguous group of cows but, due to a traumatic childhood incident involving the numbers 1 \ldots 61…6, he only wants to take a picture of a group of cows if their IDs add up to a multiple of 7.
Please help FJ determine the size of the largest group he can photograph.
给你n个数，求一个最长的区间，使得区间和能被7整除
输入输出格式
输入格式：
The first line of input contains NN (1 \leq N \leq 50,0001≤N≤50,000). The next NN
lines each contain the NN integer IDs of the cows (all are in the range
0 \ldots 1,000,0000…1,000,000).
输出格式：
Please output the number of cows in the largest consecutive group whose IDs sum
to a multiple of 7. If no such group exists, output 0.
输入输出样例
说明
In this example, 5+1+6+2+14 = 28.
思路：前缀和+二分答案。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,l,r,mid;
int num[],sum[];
bool judge(){
for(int i=;i<=n-mid;i++)
if((sum[i+mid]-sum[i])%==) return true;
return false;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&num[i]),sum[i]=sum[i-]+num[i];
l=;r=n;
while(l<=r){
mid=(l+r)/;
if(judge()) l=mid+;
else r=mid-;
}
cout<<l-;
}
80
思路：求出前缀和mod7，然后遍历，如果拥有相同的余数，说明这个区间是可以被7整除的记录。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 50010
using namespace std;
int n;
int pri[],v[];
int a[MAXN],sum[MAXN];
int main(){
scanf("%d",&n);
sum[]=;
for(int i=;i<=n;i++)
scanf("%lld",&a[i]),sum[i]=(sum[i-]+a[i])%;
for(int i=;i<=n;i++){
if(!v[sum[i]])
v[sum[i]]=i,pri[sum[i]]=i;
else pri[sum[i]]=i;
}
int ans=-;
for(int i=;i<;i++){
if(!v[i]) continue;
ans=max(ans,pri[i]-v[i]);
}
printf("%d\n",ans);
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 50010
using namespace std;
int n;
int pri[],v[];
int a[MAXN],sum[MAXN];
int main(){
scanf("%d",&n);
sum[]=;
for(int i=;i<=n;i++)
scanf("%lld",&a[i]),sum[i]=(sum[i-]+a[i])%;
for(int i=;i<=n;i++){
if(!v[sum[i]])
v[sum[i]]=i,pri[sum[i]]=i;
else pri[sum[i]]=i;
}
int ans=-;
for(int i=;i<;i++){
if(!v[i]) continue;
ans=max(ans,pri[i]-v[i]);
}
printf("%d\n",ans);
}