【TOJ 5065】最长连续子序列
程序员文章站
2022-07-02 11:46:38
Description 给定一系列非负整数,求最长的连续子序列,使其和是7的倍数。 Input 第一行为正整数N(1<=N<=50000),接下来有N行,每行有一个非负整数,所有整数不大于10^6。 Output 如果存在连续子序列,其和为7的倍数,则输出子序列长度,如果不存在则输出0。 Sampl ......
Description
给定一系列非负整数,求最长的连续子序列,使其和是7的倍数。
Input
第一行为正整数N(1<=N<=50000),接下来有N行,每行有一个非负整数,所有整数不大于10^6。
Output
如果存在连续子序列,其和为7的倍数,则输出子序列长度,如果不存在则输出0。
Sample input
7
3
5
1
6
2
14
10
Sample output
5
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int main() { int n,i,j,a[50001],right[9],left[9],maxx=0,len; cin>>n; memset(right,-1,sizeof(right)); memset(left,-1,sizeof(left)); a[0]=0; left[0]=0; for(i=1;i<n;i++) { scanf("%d",&a[i]); a[i]=(a[i-1]+a[i])%7; if(left[a[i]]==-1) left[a[i]]=i; } for(i=n-1;i>=0;i--) { if(right[a[i]]==-1) right[a[i]]=i; } for(i=0;i<=8;i++) { for(j=0;j<=8;j++) { if(right[i]>=0&&left[j]>=0&&i==j) { len=right[i]-left[j]; maxx=max(len,maxx); } } } cout<<maxx<<endl; return 0; }
下一篇: 【读书笔记】iOS-开发者证书