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

您已获得最佳的阅读体验

题目地址：P6126

题目难度：省选/NOI-

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

有只始祖鸟，我们从开始编号。对于第只始祖鸟，有个认识的朋友，它们的编号分别是。朋友的认识关系是单向的，也就是说如果第只始祖鸟认识第只始祖鸟，那么第只始祖鸟不一定认识第只始祖鸟。

聚会的地点分为两处，一处在上游，一处在下游。对于每一处聚会场所，都必须满足对于在这个聚会场所中的始祖鸟，有恰好有偶数个自己认识的朋友与之在同一个聚会场所中。当然，每一只始祖鸟都必须在两处聚会场所之一。

现在需要你给出一种安排方式。你只需要给出在上游的始祖鸟编号，如果有多组解，请输出任何一组解。如果无法满足要求，只输出一行 Impossible。

对于的数据，。

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

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

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

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

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

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

bitset<N> matrix[N];
bitset<N> ans;
int n;

void out() {
    cerr << "-----------------" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            cerr << setw(5) << matrix[i][j];
        }
        cerr << endl;
    }
    cerr << "-----------------" << endl;
}

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

        for (int i = 1; i <= n; i++) {
            // 与普通高斯消元的不同之处，对 1~n 行全部消元
            if (matrix[i].test(c) && i ^ r) {
                // 当前行不消，零行不消
                matrix[i] ^= matrix[r]; // 异或代替减法进行消元
            }
        }
        r++;
        rank++;
    }
    if (rank < n) {
        // 秩小于 n，可能是无数组解、有可能无解
        for (int i = rank + 1; i <= n; i++) {
            if (matrix[i].test(n + 1)) return 0; // 存在类似于 0=k 的矛盾情况，无解
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (matrix[i].test(j)) {
                    // 无数组解，找到主元并赋值
                    ans[j] = matrix[i][n + 1];
                    break;
                }
            }
        }
        return 1;
    }
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，对角矩阵每个未知数的解就是常数项的值
    return 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        if (k & 1) matrix[i].flip(i); // 奇数个朋友建立方程组时要算上自己
        matrix[i][n + 1] = k & 1;
        while (k--) {
            int x;
            cin >> x;
            matrix[i].flip(x);
        }
    }
    int res = gauss();
    if (res) {
        cout << ans.count() << endl;
        for (int i = 1; i <= n; i++) {
            if (ans.test(i)) cout << i << ' ';
        }
    } else cout << "Impossible" << endl;
    return 0;
}

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

P6126 [JSOI2012] - 始祖鸟 题解

P6126 [JSOI2012] - 始祖鸟题解