P2447 [SDOI2010] 高斯消元 + bitset

题意

传送门 P2447 [SDOI2010] 外星千足虫

题解

奇偶性的加减运算等价于按位异或运算，那么求解异或线性方程组即可。使用 std::bitset 优化，总时间复杂度 $O(m{n}^2/32)$。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 1E3 + 5;
typedef bitset<MAXN> bt;
int N, M, K;
bt B[MAXN];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> M;
int num = 0;
K = -1;
for (int m = 0; m < M; ++m)
{
string s;
cin >> s;
reverse(s.begin(), s.end());
bt b(s);
int x;
cin >> x;
b[N] = x;
for (int i = 0; i < N; ++i)
if (b[i] == 1 && B[i].any())
b ^= B[i];
if (!b.any())
continue;
++num;
int pos = b._Find_first();
B[pos] = b;
for (int i = 0; i < N; ++i)
if (i != pos && B[i][pos] == 1)
B[i] ^= B[pos];
if (num == N)
{
K = m + 1;
break;
}
}
if (K == -1)
{
cout << "Cannot Determinen";
return 0;
}
cout << K << 'n';
for (int i = 0; i < N; ++i)
cout << (B[i][N] == 1 ? "?y7M#" : "Earth") << 'n';
return 0;
}

最后

以上就是苹果中心为你收集整理的P2447 [SDOI2010] 高斯消元 + bitset的全部内容，希望文章能够帮你解决P2447 [SDOI2010] 高斯消元 + bitset所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。