HDU 4648 Magic Pen 6 解题报告

题意：给定一个序列，问你最多划掉多长的连续序列使得原序列和现序列%m的值相同

解题思路：解这个题有点曲折，c语言中 -3%5 = -3 ， 但是题目要求应该是 2，所以在解题的时候出现了问题，这里是有 O（n）的算法的， 利用hash表记录 前i项和 第一次出现某余数的位置，如果这个余数出现过，则可以去除掉 （我们要去掉m的倍数），然后取最长的就可以了。

解题代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

//#define DEBUG

const int maxn = 100000 + 5;

int dp[maxn];
int hs[maxn];


int main()
{

    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        memset(hs,-1,sizeof(hs));
        for (int i = 1; i <= n; i++)
            scanf("%d", &dp[i]);
        hs[0] = 0;
        int MAX = 0  ;
        for (int i = 1; i <= n; i++)
        {
            dp[i] += dp[i - 1];
            dp[i] %= m;
            if(dp[i] < 0 )
                dp[i] = m + dp[i];
            if(hs[dp[i]] != -1)
            {
               if(i - hs[dp[i]]  > MAX)
                MAX = i - hs[dp[i]];
            }
            else
            {
               hs[dp[i]] = i;
            }
        }
        printf("%d
", MAX);
    }
    return 0;
}