我是靠谱客的博主 苹果中心,这篇文章主要介绍P2447 [SDOI2010] 高斯消元 + bitset,现在分享给大家,希望可以做个参考。

题意

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

题解

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(83)

评论列表共有 0 条评论

立即
投稿
返回
顶部