「SDOI2010」外星千年虫 - 高斯消元

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

研究人员从外星带来了外星千年虫。他们发现，外星千年虫的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足，但足的总数一定是奇数条！

虽然从外观难以区分二者，但通过统计足的数目，科学家们就能根据奇偶性判断出千足虫所属的星球。

作为 J 国派去 NASA 的秘密间谍，你希望参加这次研究活动以掌握进一步的情报，而 NASA 选拔的研究人员都是最优秀的科学家。于是 NASA 局长 Charles Bolden 出了一道难题来检测你的实力：

现在你面前摆有 \(1\ldots N\) 编号的 \(N\) 只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。

Charles 每次会在这 \(N\) 只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出其内所有昆虫足数之和。Charles 会将这个和数 \(\bmod\) \(2\) 的结果反馈给你，同时告诉你一开始放入机器中的是哪几只虫子。

他的这种统计操作总共进行 \(M\) 次，而你应当尽早得出鉴定结果。

假如在第 \(K\) 次统计结束后，现有数据就足以确定每只虫子的身份，你就还应将这个 \(K\) 反馈给 Charles，此时若 \(K<M\)，则表明那后 \(M-K\) 次统计并非必须的。

如果根据所有 \(M\) 次统计数据还是无法确定每只虫子身份，你也要跟 Charles 讲明：就目前数据会存在多个解。

解题思路

我们假设外星千年虫有 \(1\) 个足，地球千年虫有 \(0\) 个足，则该题可表示为求下列方程的解（其中 \(\forall x_{i, j}, b_i \in \{ 0, 1 \}\)）：

\[ \begin{cases} \oplus_{i = 1}^nx_{1, i}a_i = b_1 \\ \oplus_{i = 1}^nx_{2, i}a_i = b_2 \\ \cdots \\ \oplus_{i = 1}^nx_{m, i}a_i = b_m \\ \end{cases} \]

于是我们将这道题转化为异或方程组求解问题。异或可看成不进位的加减法，同样可使用高斯消元求解。本题还需要统计最少使用方程数，我们只需在每次选择在处理 \(a_i\) 时选择 \(x_{j, i} = 1\) 且 \(j\) 最小的项交换，并统计所有对应的 \(j\) 的最大值即可。

在高斯消元时可使用 std::bitset 优化代码。

代码演示

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
#include <cstdio>
#include <bitset>

const int MAXN = 1e3;
const int MAXM = 2e3;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    static char s[MAXN + 2];
    static std::bitset<MAXN + 1> a[MAXM + 2];
    for (int i = 1; i <= m; i++) {
        int in;
        scanf("%s %d", s + 1, &in);
        a[i][n + 1] = in;
        for (int j = 1; j <= n; j++) a[i][j] = s[j] - '0';
    }

    int max = n;
    for (int i = 1; i <= n; i++) {
        max = std::max(max, i);
        if (!a[i][i]) {
            for (int j = i + 1; j <= m; j++) {
                if (a[j][i]) {
                    std::swap(a[i], a[j]);
                    max = std::max(max, j);
                    break;
                }
            }
        }
        if (a[i][i] == 0) {
            puts("Cannot Determine");
            return 0;
        }
        for (int k = m; k > i; k--) {
            if (a[k][i]) {
                a[k] ^= a[i];
            }
        }
    }

    for (int i = n; i; i--) {
        for (int j = i - 1; j; j--) {
            if (a[j][i]) {
                a[j] ^= a[i];
            }
        }
    }

    printf("%d\n", max);
    for (int i = 1; i <= n; i++) {
        if (a[i][n + 1]) puts("?y7M#");
        else puts("Earth");
    }

    return 0;
}