【题解】bzoj1923

题目大意

请输入图片描述

解题过程

思路

异或方程组,高斯消元,使用bitset优化。在对$a_{i,j}$消元时注意向下取到最小的$p$

代码

#include <bitset>
#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
bitset<1010> f[2005];

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x; char c;
        for (int j = 1; j <= n; j++) {
            cin >> c;
            f[i][j] = (c ^ 48);
        }
        cin >> c;
        f[i][n + 1] = c ^ 48;
    }
    int w, ans = 0;
    for (int i = 1; i <= n; i++) {
        w = i;
        while (w <= m && !f[w][i]) ++w;
        if (w == m + 1) {
            cout << "Cannot Determine" << endl;
            return 0;
        }
        ans = max(ans, w);
        swap(f[w], f[i]);
        for (int j = 1; j <= m; j++) {
            if (i == j or !f[j][i]) continue;
            f[j] ^= f[i];
        }
    }
    cout << ans << endl;
    for (int i = 1; i <= n; i++) {
        if (f[i][n + 1]) cout << "?y7M#" << endl;
        else cout << "Earth" << endl;
    }
    return 0;
}