题目传送门: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:这份代码是在线的做法,看题解,貌似离线也是可以做的。