P6126 [JSOI2012] - 始祖鸟题解 - JustPureH2O 的博客

Done

您已获得最佳的阅读体验！

题目地址：P6126

题目难度：省选/NOI-

题目来源：江苏 2012 各省省选

有只始祖鸟，我们从开始编号。对于第只始祖鸟，有个认识的朋友，它们的编号分别是。朋友的认识关系是单向的，也就是说如果第只始祖鸟认识第只始祖鸟，那么第只始祖鸟不一定认识第只始祖鸟。
聚会的地点分为两处，一处在上游，一处在下游。对于每一处聚会场所，都必须满足对于在这个聚会场所中的始祖鸟，有恰好有偶数个自己认识的朋友与之在同一个聚会场所中。当然，每一只始祖鸟都必须在两处聚会场所之一。
现在需要你给出一种安排方式。你只需要给出在上游的始祖鸟编号，如果有多组解，请输出任何一组解。如果无法满足要求，只输出一行 Impossible。
对于的数据，。

为所有始祖鸟按朋友数的奇偶性分类。对于朋友数是偶数的始祖鸟，只要在上游/下游出现偶数个朋友，那么另一方也肯定存在偶数个朋友，此时当前的始祖鸟就可以在上下游中任意选择去向；如果这只始祖鸟有奇数个朋友，那么上游/下游一定是一边奇数一边偶数，此时这只鸟只能去偶数那侧。

若当前始祖鸟在上游，我们令，否则。对于朋友数是偶数的始祖鸟，把它的所有朋友代表的数异或起来，那就相当于偶数个与偶数个异或，结果为；对于朋友数是奇数的始祖鸟，把自己和它的朋友代表的数异或起来，相当于偶数个和奇数个异或，结果一定是。因此对于某只有个朋友的始祖鸟，一定有如下关系：

然后对每只始祖鸟建立关系，再使用异或高斯消元即可。这里介绍一种能方便解决“无数组解特解求解”问题的消元法。

一般的高斯消元会把矩阵消元成一个上/下三角矩阵，矩阵的同一列可能存在多个非零的系数，也就代表着方程之间的未知数还存在相互依赖关系，求解时只能老老实实向上回代，遇到存在自由元的情况时会较难处理。

我们认为这样的矩阵是“未完全化简的”，事实上，如果在减法/异或消元时让每一行都重新消元一次，而不是只对行消元，那么最终你会得到一个同一列只存在一个非零系数的增广矩阵。特别地，对于存在唯一解的情况，它是一个对角矩阵，此时每个未知数的解就是对应常数项的值；如果是存在无数组解的情况，找到主元也非常简单：只需找到每一行的第一个非零系数，然后直接将它赋值为常数项。对于主元右侧的所有非零系数，一律当自由元赋值为即可。

1
#include <bits/stdc++.h>
2
#define N 2010
3
using namespace std;
4

5
bitset<N> matrix[N];
6
bitset<N> ans;
7
int n;
8

9
void out() {
10
    cerr << "-----------------" << endl;
11
    for (int i = 1; i <= n; i++) {
12
        for (int j = 1; j <= n + 1; j++) {
13
            cerr << setw(5) << matrix[i][j];
14
        }
15
        cerr << endl;
16
    }
17
    cerr << "-----------------" << endl;
18
}
19

20
int gauss() {
21
    int rank = 0; // 矩阵的秩
22
    for (int c = 1, r = 1; c <= n; c++) {
23
        int t = r;
24
        for (int i = r; i <= n; i++) {
25
            if (matrix[i].test(c)) {
26
                // 找到绝对值最大的行（只要第一个系数是 1 即可）
27
                t = i;
28
                break;
29
            }
30
        }
31
        if (!matrix[t].test(c)) continue; // 跳过零行
32
        if (t ^ r) swap(matrix[r], matrix[t]); // 交换到第一行
33

34
        for (int i = 1; i <= n; i++) {
35
            // 与普通高斯消元的不同之处，对 1~n 行全部消元
36
            if (matrix[i].test(c) && i ^ r) {
37
                // 当前行不消，零行不消
38
                matrix[i] ^= matrix[r]; // 异或代替减法进行消元
39
            }
40
        }
41
        r++;
42
        rank++;
43
    }
44
    if (rank < n) {
45
        // 秩小于 n，可能是无数组解、有可能无解
46
        for (int i = rank + 1; i <= n; i++) {
47
            if (matrix[i].test(n + 1)) return 0; // 存在类似于 0=k 的矛盾情况，无解
48
        }
49
        for (int i = 1; i <= n; i++) {
50
            for (int j = 1; j <= n + 1; j++) {
51
                if (matrix[i].test(j)) {
52
                    // 无数组解，找到主元并赋值
53
                    ans[j] = matrix[i][n + 1];
54
                    break;
55
                }
56
            }
57
        }
58
        return 1;
59
    }
60
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，对角矩阵每个未知数的解就是常数项的值
61
    return 2;
62
}
63

64
int main() {
65
    ios::sync_with_stdio(false);
66
    cin.tie(nullptr);
67
    cout.tie(nullptr);
68

69
    cin >> n;
70
    for (int i = 1; i <= n; i++) {
71
        int k;
72
        cin >> k;
73
        if (k & 1) matrix[i].flip(i); // 奇数个朋友建立方程组时要算上自己
74
        matrix[i][n + 1] = k & 1;
75
        while (k--) {
76
            int x;
77
            cin >> x;
78
            matrix[i].flip(x);
79
        }
80
    }
81
    int res = gauss();
82
    if (res) {
83
        cout << ans.count() << endl;
84
        for (int i = 1; i <= n; i++) {
85
            if (ans.test(i)) cout << i << ' ';
86
        }
87
    } else cout << "Impossible" << endl;
88
    return 0;
89
}

Hack 数据也过了，这是记录。你可以调用函数 out() 来输出矩阵的项。

音乐

音乐

评论区

音乐

目录

音乐

音乐

P6126 [JSOI2012] - 始祖鸟 题解

评论区

音乐

目录

P6126 [JSOI2012] - 始祖鸟题解