Description
给你一个数 $n$ 和 $n$ 个数 $a_1$ ~ $a_n$ ，现在请你求出这 $n$ 个数的一个非空子集，使得这个子集中的数的和能被 $n$ 整除，无解输出 -1 ，共有 $T$ 组数据。
下文将用 $|x|$ 来表示 $x$ 的绝对值。
Solution
设 $s_i$ 表示 $(\sum_{j = 1} ^ i a_i) \mod n$ ，那么 $s_i$ 的取值范围为 $[0, n)$ 。
所以我们可以用鸽巢原理证明出在 $s_1$ ~ $s_n$ 中至少有两个是相同的。
因此至少存在一段连续的数满足要求。
所以问题就被转化为了在原序列中找出连续的一段，使它的和能够被 $n$ 整除。
用 前缀和 加 桶 即可解决。
时间复杂度 $O(Tn)$ 。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <cstdio>
#include <cstring>
#define maxN 200010
long long cnt[maxN], su[maxN], a[maxN];
long long min (long long x, long long y)
{
return x < y ? x : y;
}
long long max (long long x, long long y)
{
return x > y ? x : y;
}
int main ()
{
long long T = 0;
scanf("%lld", &T);
while(T--)
{
memset(cnt, 0, sizeof(cnt));
long long n = 0;
scanf("%lld", &n);
su[0] = 0;
for(long long i = 1;i <= n; i++)
{
scanf("%lld", &a[i]);
su[i] = su[i - 1] + a[i];
su[i] %= n;
}
long long mi = 2147483647;
long long ma = -2147483647;
for(long long i = 0;i <= n; i++)
{
mi = min(mi, su[i]);
ma = max(ma, su[i]);
}
for(long long i = 0;i <= n; i++)
{
su[i] -= mi;
}
for(long long i = 0;i <= n; i++)
{
if(!cnt[su[i]])
{
cnt[su[i]] = i + 1;
}
else
{
printf("%lld\n", i - cnt[su[i]] + 1);
for(long long j = cnt[su[i]];j <= i; j++)
{
printf("%lld ", a[j]);
}
printf("\n");
break;
}
}
}
return 0;
}
|