洛谷题单指南-基础线性代数-P2447 [SDOI2010] 外星千足虫

原题链接：https://www.luogu.com.cn/problem/P2447

题意解读：有n只虫子，地球虫用0表示，外星虫用1表示，给出若干组测试，计算每只虫子的种类。

解题思路：

设x_i表示第i只虫子的类别，a_ij表示第i行第j个字符是0还是1，b_i表示第i行的值

那么问题可以转换成异或方程组：

a₁₁x₁^a₁₂x₂^...^a_1nx_n = b₁

a₂₁x₁^a₂₂x₂^...^a_2nx_n = b₂

....

a_m1x₁^a_m2x₂^...a_mnx_n = b_m

异或操作就是不进位的加法，所以异或方程组同样可以用高斯消元来求解。

注意：

1、题目要求最少需要几步，也就是最少前几个方程组就能确定答案，只需记录最大的处理行即可

2、传统的高斯消元时间复杂度是O(mnn)，此题会超时，可以用过bitset来存储矩阵的行，借助于bitset的异或操作来优化

100分代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1005, M = 2005;
int n, m, k;
bitset<N> a[M];int gauss()
{int row = 0; //当前行for(int col = 0; col < n; col++) //枚举当前列{int t = row;while(t < m && a[t].test(col) != 1) t++; //找到当前列绝对值最大的行,异或方程就是第一个为1的行k = max(k, t);if(a[t].test(col) == 0) continue; //如果当前列最大的行是0，则继续枚举下一列if(t != row) swap(a[t], a[row]); //将当前列绝对值最大的行与当前行交换for(int i = 0; i < m; i++) //将当前列的其它行消成0if(i != row && a[i].test(col) == 1) a[i] ^= a[row];row++; //继续下一行}if(row < n) return 0; //无穷多解return 1; //唯一解
}int main()
{cin >> n >> m;for(int i = 0; i < m; i++){string arg;int value;cin >> arg >> value;for(int j = 0; j < n; j++){a[i].set(j, arg[j] == '1');}a[i].set(n, value);}int res = gauss();if(res == 1){cout << k + 1 << endl;for(int i = 0; i < n; i++){if(a[i].test(n) == 0) cout << "Earth" << endl;else cout << "?y7M#" << endl;}}else cout << "Cannot Determine";return 0;
}