BZOJ1923外星千足虫(高斯消元):高斯消元求解异或方程组和普通消元的思路差不多,同样是找到一个可用的交换,然后把原来的加减运算全部改为异或。
如果a(i,i)无法交换成0的话,说明这里有可能出现无解或多解,那么回代的时候判断一下剩下的常数项和b(i)是否相等就可以了
不过这道题保证一定有解,所以出现上面的情况就一定有多解,直接返回就行了
注意交换的时候记录一下最多用到的方程k
安利一个讲解:解线性方程组——高斯消元の板子
#include#include #include #include #include #include using namespace std; #define N 2005 char s[N]; int n,m,k; bool flag; bitset a[N]; int b[N],ans[N]; void gauss() { for (int i=1;i<=n;++i) { if (a[i][i]==0) { int num=i; for (int j=i+1;j<=m;++j) if (a[j][i]) {num=j;break;} if (num==i) {flag=true;return;} swap(a[i],a[num]);swap(b[i],b[num]); k=max(k,num); } for (int j=i+1;j<=m;++j) if (a[j][i]) a[j]^=a[i],b[j]^=b[i]; } for (int i=n;i>=1;--i) { ans[i]=b[i]; for (int j=i;j>=1;--j) if (a[j][i]) b[j]^=ans[i]; } } int main() { scanf("%d%d",&n,&m);k=n; for (int i=1;i<=m;++i) { scanf("%s",s);scanf("%d",&b[i]); for (int j=1;j<=n;++j) a[i][j]=s[j-1]-'0'; } gauss(); if (flag) puts("Cannot Determine"); else { printf("%d\n",k); for (int i=1;i<=n;++i) { if (ans[i]) puts("?y7M#"); else puts("Earth"); } } }