题目
p2447 [sdoi2010]外星千足虫
解析
sol写到自闭,用文字描述描述了半个小时没描述出来,果然还是要好好学语文
用高斯消元求解异或方程组。
因为
- (奇数bigoplus奇数=偶数)
- (偶数bigoplus偶数=偶数)
- (奇数bigoplus偶数=奇数)
(0)为偶数,(1)为奇数,
- ((奇数+奇数)mod 2=0)
- ((偶数+偶数)mod 2=0)
- ((奇数+偶数)mod 2=1)
若把第一个里面的奇偶数分别换成(1)和(0),则对于((x_1+x_2)bmod 2)的操作,可以看做异或操作((x_1bigoplus x_2))。
易证,((x_1+x_2+x_3+···+x_n)mod 2 = x_1bigoplus x_2bigoplus x_3 bigoplus ···bigoplus x_n)。
对于主元所在的列,我们只让主元行上的数为(1),其余的为(0),于是我们让每一行与当前主元行比较,若某一行的这个数为(1),就让这一行异或主元行。
因为我们之前处理当前主元行以上的内容时,把除了当时主元行上的所有当时主元所在列上的数都异或成了(0),所以我们当前主元行主元之前的数都为0,根据异或的性质,发现当前主元行前面的(0)对之前处理的行没有影响,这样更新到最后,我们会得到一个单位矩阵,
其实手动一模拟就出来了。。
如[begin{bmatrix} 0&1&1&mid&1\ 1&0&1&mid&0\ 0&0&1&mid&1 end{bmatrix} tobegin{bmatrix} 1&0&1&mid&0\ 0&1&1&mid&1\ 0&0&1&mid&1 end{bmatrix} tobegin{bmatrix} 1&0&0&mid&1\ 0&1&0&mid&0\ 0&0&1&mid&1 end{bmatrix}\]
于是就得到了答案。
代码
#include <bits/stdc++.h> using namespace std; const int n = 2010; bitset<n> a[n]; char s[n]; int n, m, ans; template<class t>inline void read(t &x) { x = 0;int f = 0;char ch = getchar(); while(!isdigit(ch)) f |= (ch == '-'),ch = getchar(); while(isdigit(ch)) x = x * 10 + ch -'0',ch = getchar(); x = f ? -x : x; return ; } void gauss() { for (int i = 1; i <= n; ++i) { int k = i; while (!a[k][i] && k <= m) k++; if (k == m + 1) { ans = -1; return; } ans = max(ans, k); if (k != i) swap(a[k], a[i]); for (int j = 1; j <= m; ++j) if (j != i && a[j][i]) a[j] ^= a[i]; } return; } int main() { read(n), read(m); for (int i = 1, x; i <= m; ++i) { scanf("%s", s); for (int j = 0; j < n; ++j) a[i][j + 1] = s[j] - '0'; read(x); a[i][n + 1] = x; } gauss(); if (ans == -1) printf("cannot determinen"); else { printf("%dn", ans); for (int i = 1; i <= n; ++i) printf(a[i][n + 1] == 1 ? "?y7m#n" : "earthn"); } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603966.html