hdu - 4648 - Magic Pen 6
1487 ワード
題意:N個の数があって、最大で何個の連続する数([-10000000,10000000])を取り出すことができることを聞いて、残った数の和模Mの値がもとのN個の数の和模Mの値(0タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4648
——>>前i項と、前i項とモジュールMを求めてrとし、rが最初に現れた位置Lと最後に現れた位置Rをマークします.では、(L,R)という区間を削除すると、元のシーケンスとモジュールMには影響がありません.
注意:-5%3=?、ここでは-5%3=1で計算できます.
特に注意:このN個の数の下付き文字が1から始まると、0が最も早く現れる位置は0がシーケンスの中で最も早く現れる位置ではなく、下付き文字0という位置である(0が初めてi位に現れると仮定すると、前のi個の数を取ってもいいのではないか).
——>>前i項と、前i項とモジュールMを求めてrとし、rが最初に現れた位置Lと最後に現れた位置Rをマークします.では、(L,R)という区間を削除すると、元のシーケンスとモジュールMには影響がありません.
注意:-5%3=?、ここでは-5%3=1で計算できます.
特に注意:このN個の数の下付き文字が1から始まると、0が最も早く現れる位置は0がシーケンスの中で最も早く現れる位置ではなく、下付き文字0という位置である(0が初めてi位に現れると仮定すると、前のi個の数を取ってもいいのではないか).
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 10;
int L[maxn], R[maxn];
bool vis[maxn];
int main()
{
int N, M, a, r, i;
while(scanf("%d%d", &N, &M) == 2){
memset(vis, 0, sizeof(vis));
long long sum = 0;
for(i = 1; i <= N; i++){
scanf("%d", &a);
sum += a;
r = (sum % M + M) % M;
if(!vis[r]){
vis[r] = 1;
L[r] = i;
}
R[r] = i;
}
L[0] = 0; // ， WA！
int Max = 0;
if(r == 0) Max = N;
else for(i = 0; i < M; i++) if(vis[i]) Max = max(Max, R[i] - L[i]);
printf("%d
", Max);
}
return 0;
}