信息
- ID
- 198
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 268
- 已通过
- 38
- 上传者
u1s1,这题没见过确实不太好想 (所以数据造的很水,直接深搜都能获得很高的分数) 。
题目的意思就是给定 n 个正整数,求从其中选出任意个数,使得这些数的和为 n 的倍数。
如果没看懂的话就再解释一下。根据上述证明,若存在 si 为 n 的倍数,则选择前 i 个数即可;否则,对于除以 n 余数相同的 si 与 sj ,选择区间 [i+1,j] 即可。
#include <cstdio>
#include <iostream>
const int N = 1e6 + 5;
int A[N], r[N];
void print(int st, int ed) {
printf("%d\n", ed - st + 1);
for (int i = st; i <= ed; ++i) {
printf("%d%c", A[i], i == ed ? '\n': ' ');
}
}
int main() {
int n; scanf("%d", &n);
int rr = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
rr = (rr + A[i]) % n;
if (rr == 0) {
print(1, i);
break;
} else if (r[rr]) {
print(r[rr] + 1, i);
break;
} else r[rr] = i;
if (i == n) puts("No"); // impossible
}
return 0;
}