TOJ 5065: 最长连续子序列

5065: 最长连续子序列  

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 140            Accepted:29

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

这个题很水？所以大神懒得讲他们的做法？不过这道题确实不难，也就是O(n)做法就可以过的，没有想到这种贪心

这个其实是同余的思想，就是余数相同相当于中间这段也是，只要记录这个余数最早和最晚出线的就是所求值

https://ac.nowcoder.com/acm/contest/91/L 这个题目数据水了，全是连续的，当然正解是DP，序列是不连续的，子串是连续的埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛

#include <stdio.h>
int a[50005];
int main(){
int n,i,j,k,p,m=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
    scanf("%d",&p);
    a[i]=(a[i-1]+p)%7;
}
for(i=0;i<7;i++){
    for(k=0;k<=n;k++){
        if(a[k]==i){
        break;}
    }
    for(j=n;j>0;j--){
    if(a[j]==i){
    break;}
    }
    if(j-k>m)m=j-k;
}
printf("%d",m);
return 0;}

这份代码逻辑更好些

#include <stdio.h>
int a[7],b[7];
int main()
{
    int n;
    scanf("%d",&n);
    int s=0;
    for(int i=1; i<=n; i++)
    {
        int p;
        scanf("%d",&p);
        s=(s+p)%7;
        if(!a[s]&&s)a[s]=i;
        b[s]=i;
    }
    int mi=0;
    if(b[0])
    mi++;
    for(int i=0; i<7; i++)
    {
        if(b[i]-a[i]>mi)
            mi=b[i]-a[i];
    }
    printf("%d",mi);
    return 0;
}