外星千足虫
这题是一道高斯消元的模线性方程组,由于mod=2,只会出现0和1
由于题目要我们找到前k个可以确定解的方程,而且只有0和1出现,我们需要借助异或空间线性基来求解(本质上就是找到前k个线性无关的方程组)
还有一个问题,这道题的n很大(1000),要是直接高斯消元会超时
因此,我们采取bitset优化
代码如下:
#include<iostream>
#include<bitset>
#include<vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<bitset<1005>>basic(n + 1);
int rank = 0;
int k = -1;
for (int idx = 1;idx <= m;idx++) {
string str;int val;
cin >> str >> val;
bitset<1005>cur;
for (int i = 0;i < str.size();i++) if (str[i] == '1') cur.set(i);
if (val) cur.set(n);
for (int i = 0;i < n;i++) {
if (cur[i]) {
if (basic[i].none()) {
basic[i] = cur;
rank++;
if (rank == n) k = idx;
break;
}
else {
cur ^= basic[i];
}
}
}
}
if (rank < n) {
cout << "Cannot Determine";
return 0;
}
vector<int>ans(n,0);
for (int i = n - 1;i >= 0;i--) {
int sum = basic[i][n];
for (int j = i + 1;j < n;j++) {
if (basic[i][j]) sum ^= ans[j];
}
ans[i] = sum;
}
cout << k << '\n';
for (int num : ans) {
if (num) cout << "?y7M#\n";
else cout << "Earth\n";
}
}
时间复杂度:O(n * n * m / 64)
空间复杂度:O(n * m)