hdu - 4648 - Magic Pen 6

2019-04-13 16:18发布

站内文章 / 模拟电子
12491 0 1222
题意：有N个数，问最多能取出多少个连续的数([-100000000, 100000000])，使得剩下的数的和模M的值等于原来N个数的和模M的值(0 < N <= 100000, 0 < M < 10000)。 题目链接：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个数拿掉，是不是可以？）。 #include #include #include 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; }

热门文章