hdu 4648 Magic Pen 6 多校的一個題目

題目是說給你N個數再給一個MOD 這N個數的和對MOD取模的值是K問你可以從這N個數中最多刪除多少個連續的數使得剩下的數的和模上MOD的結果不變還是K

這題數據范圍有點大，不過有O(N)的算法就可以搞定了。

方法    題意轉化一下就是： 給出一列數a[1]...a[n]，求長度最長的一段連續的數，使得這些數的和能被M整除。 分析：設這列數前i項和為s[i],則一段連續的數的和 a[i]+a[i+1]+...+a[j-1]+a[j]=s[j]-s[i-1]，所以這段連續的數的和能被m整除的條件就是 (s[j]-s[i-1]) % m == 0，即 s[j]%m-s[i-1]%m == 0，因此，只需要每一個余數找使s[i]%m等於該余數的最小的i，和s[j]%m等於該余數的最大的j，相減即為最長的連續的數的長度。

代碼就比較簡單了，只要記錄最先出現的不同和得下標就可以很快做出來的,代碼精簡了sum數組和原數據的數組，可能會有點難懂。。其中v數組的應用是關鍵，挺好的，這個方法

#include<stdio.h>
#include<string.h>
inline int max(int a,int b) {return a>b? a:b;}
int N,M,a,v[10005],ans,sum,i,pre;//pre是用來記錄sum[i-1]的而sum記錄的是sum[i]
// v數組的v[i]記錄的是第一次出現前綴和為i時其對應的下標，若沒出現過就是-1
int main()
{
    while(~scanf("%d%d",&N,&M))
    {
        memset(v,-1,sizeof(v));
        pre=v[0]=sum=ans=0;
        for(i=1;i<=N;++i)
        {
            scanf("%d",&a);
            sum=(pre+a)%M;
            sum=(sum+M)%M;//因為有負數，取模的時候要注意一下的
            if(v[sum]==-1) v[sum]=i;
            ans=max(ans,i-v[pre=sum]);
        }
        printf("%d\n",ans);
    }
    return 0;
}