【BZOJ 1923】[Sdoi2010] 外星千足虫

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1923
数据生成器:http://paste.ubuntu.com/18996088/

今天在做高斯消元的专题。一看这题,欸,这不高斯消元求解异或方程组的板题吗? (~ ̄▽ ̄)→))* ̄▽ ̄*)o
于是写了一写,果然是板题。然而我想只有我这种纸张才会因为把结果输反了而wa了半天吧?QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

const int MAXN = 1000+9;

int n,m,mat[MAXN][MAXN],tmp[MAXN],cnt;
char pat[MAXN],tag[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline bool update(){
	for (int i=1;i<=n;i++) if (tmp[i]){
		if (!tag[i]) {
			tag[i] = 1; cnt++;
			for (int j=1;j<=n+1;j++) 
				mat[j][i] = tmp[j];
			return cnt == n;
		} else for (int j=1;j<=n+1;j++) tmp[j] ^= mat[j][i];
	}
	return cnt == n;
}

inline void output(int k){
	printf("%d\n",k);
	for (int i=n;i;i--){
		int ans = mat[n+1][i];
		for (int j=i+1;j<=n;j++)
			ans ^= mat[j][i];
		if (ans) tag[i] = 1;
		else tag[i] = 0;
		for (int j=i-1;j;j--)
			mat[i][j] *= ans;	
	}
	for (int i=1;i<=n;i++) 
		if (tag[i]) puts("?y7M#");
		else puts("Earth");
}

int main(){
	scanf("%d%d",&n,&m);
	for (int k=1;k<=m;k++){
		scanf("%s",pat+1); tmp[n+1]=read();
		for (int i=1;i<=n;i++)
			tmp[i] = pat[i]-'0';
		if (update()) output(k), exit(0);
	}
	puts("Cannot Determine\n");
	return 0;
} 

PS:这份代码是在线的做法,看题解,貌似离线也是可以做的。