题解 P2447 【[SDOI2010]外星千足虫】
YoungNeal
2018-07-03 21:41:01
题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9260782.html)效果更佳哦~
## Solution
显然要高斯消元解异或方程组。
这题 $N$ 有点大，可以用 $bitset$ 优化。
最开始想的是二分找这个满足要求的最小的 $K$，无奈复杂度过不去。
考虑高斯消元的过程，假设当前在消第 $i$ 列，第 $j$ 行，那么一定是从第 $j$ 行向下找一个最小的 $p$ ，满足 $a[p][i]=1$。这里的**最小的**就已经满足题目要求了，不必要在二分了。也就是说，每次 $swap$ 时取一个 $\max$ 即可。
其他就跟高斯消元一模一样了。
## Code
```cpp
#include<cstdio>
#include<cctype>
#include<bitset>
#define N 1005
#define M 2005
#define bi std::bitset<N>
#define max(A,B) ((A)>(B)?(A):(B))
int n,m;
bi a[M];
int getint(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void swap(bi &x,bi &y){bi t=x;x=y;y=t;}
signed main(){
n=getint(),m=getint();
for(int i=1;i<=m;i++){
int x;
for(int j=1;j<=n;j++){
scanf("%1d",&x);
a[i][j]=x;
}
x=getint();a[i][n+1]=x;
}
int now,ans=0;
for(int i=1;i<=n;i++){
now=i;
while(now<=m and !a[now][i])
now++;
if(now==m+1){
printf("Cannot Determine");
return 0;
}
ans=max(ans,now);
if(now!=i)
swap(a[now],a[i]);
for(int j=1;j<=m;j++){
if(j==i)
continue;
if(!a[j][i])
continue;
a[j]^=a[i];
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
if(a[i][n+1])
printf("?y7M#\n");
else
printf("Earth\n");
}
return 0;
}
```