HDU 4648 Magic Pen 6 思路

官方题解：

题意转化一下就是：

给出一列数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，相减即为最长的连续的数的长度。

i 要从1开始，不然会WA。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int MAXN = ;

int n, mod;

int maxPos[MAXN];

int minPos[MAXN];

int main()

{

    //freopen( "1006.in", "r", stdin );

    //freopen( "s.txt", "w", stdout );

    while ( ~scanf( "%d%d", &n, &mod ) )

    {

        memset( maxPos, -, sizeof(maxPos) );

        memset( minPos, -, sizeof(minPos) );

        int sum = ;

        minPos[] = ;

        for ( int i = ; i <= n; ++i )

        {

            int a;

            scanf( "%d", &a );

            sum += a;

            sum %= mod;

            if ( sum <  ) sum += mod;

            if ( minPos[sum] == - )

                minPos[sum] = i;

            maxPos[sum] = i;

        }

        int ans = ;

        for ( int i = ; i < mod; ++i )

            if ( maxPos[i] != - && minPos[i] != - )

            {

                ans = max( ans, maxPos[i] - minPos[i] );

            }

        printf( "%d\n", ans );

    }

    return ;

}

巴特西

HDU 4648 Magic Pen 6 思路

最新文章

热门文章