题目描述
有 $n+1$ 个数 ${a_i}$，分成 $k$ 组，其中第 $i$ 组分得的数之和必须为 $s_i$ 的倍数，保证 $\sum s_i=n+1$，第 $n+1$ 个数丢失，要给出任一满足条件的 $a_{n+1}$ 的值和分组方案。
$1\le n,k\le 200$，$1\le a_i\le 10^6$。
算法分析
有一个称为 Erdős–Ginzburg–Ziv theorem 的结论，它说任意 $2n-1$ 个数一定能选出 $n$ 个数是 $n$ 的倍数。
我们将 $s_i$ 排序，那么有 $s_1\le s_2\le\dots\le s_k$，假设选到第 $i$ 个数，一定有 $\sum_{k=i}^ns_k\gt2s_i-1$，这表明前 $k-1$ 组的方案一定存在，对于第 $k$ 组我们保留了 $a_{n+1}$ 用于弥补余数使它整除 $s_k$，因此不存在无解的情况。
考虑用 DP 的方法先将前 $k-1$ 组的方案分别求出，就可以构造出第 $k$ 组的方案了。
问题转化为当前有 $a_0$ 个整数 $a_1,a_2,\dots,a_{a_0}$，从中选出 $s_i$ 个数，使这些数的和整除 $s_i$ 的任一方案。
设 $f[x][y][z]$ 表示前 $x$ 个整数中能否选出 $y$ 个数使得这些数模 $s_i$ 的余数为 $z$，转移考虑第 $i$ 个数填或者不填两种情况。
如何得到方案数呢？首先，正序依次贪心取很可能最后得不到解。逆序的话，$f[x][y][z]$ 存在解并不代表 $x$ 应当被选，因为它可能是从 $f[x-1][y][z]$ 转移而来的（即前面的数被选，对应状态中表示的前 $x$ 个整数，但倘若不这样设计状态转移的复杂度就不能够做到 $O(1)$）。这里我们判断如果 $f[x-1][y][z]$ 为 false，$f[x][y][z]$ 为 true 时才选择 $x$。
也可以判断它不能够从 $x$ 被选的上一个状态转移而来，即将代码实现中第 $35$ 行的 f[x - 1][y][z] 改为 !f[x - 1][y - 1][(z + si - (a[x] % si)) % si]，分别对应可任取的两种方案。
时间复杂度大约是 $O(n^4)$。
代码实现
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
60
| #include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <algorithm>
#define N 205
typedef std::pair<int, int> P;
int a[N], tmp[N]; P s[N]; bool f[N][N][N];
std::vector<int> ans[N];
int main() {
int n, k; scanf("%d %d", &n, &k);
a[0] = n; for(int i = 1; i <= n; ++i) scanf("%d", a + i);
for(int i = 1; i <= k; ++i) {
scanf("%d", &s[i].first);
s[i].second = i;
}
std::sort(s + 1, s + 1 + k);
for(int i = 1; i < k; ++i) {
int si = s[i].first, idx = s[i].second;
memset(f, 0, sizeof(f)); f[0][0][0] = true;
for(int x = 1; x <= a[0]; ++x) {
for(int y = 0; y <= si; ++y) {
for(int z = 0; z < si; ++z) {
f[x][y][z] = f[x - 1][y][z];
if(y > 0) {
f[x][y][z] |= f[x - 1][y - 1][(z + si - (a[x] % si)) % si];
}
}
}
}
tmp[0] = 0;
for(int x = a[0], y = si, z = 0; x >= 1; --x) {
if(!y || !f[x][y][z] || f[x - 1][y][z]) {
tmp[++tmp[0]] = a[x];
continue;
}
--y; z = (z + si - a[x] % si) % si;
ans[idx].push_back(a[x]);
}
for(int i = 0, end = tmp[0]; i <= end; ++i) a[i] = tmp[i];
}
int si = s[k].first, idx = s[k].second, sum = 0;
for(int x = 1; x <= a[0]; ++x) {
sum = (sum + a[x]) % si;
ans[idx].push_back(a[x]);
}
ans[idx].push_back(si - sum);
printf("%d\n", si - sum);
for(int i = 1; i <= k; ++i) {
for(int j = 0, end = ans[i].size(); j < end; ++j) {
printf("%d%c", ans[i][j], (j ^ (end - 1)) ? ' ' : '\n');
}
}
return 0;
}
|