题解 P2447 【[SDOI2010]外星千足虫】

· · 题解

题解在博客食用效果更佳哦~

Solution

显然要高斯消元解异或方程组。

这题 N 有点大，可以用 bitset 优化。

最开始想的是二分找这个满足要求的最小的 K，无奈复杂度过不去。

考虑高斯消元的过程，假设当前在消第 i 列，第 j 行，那么一定是从第 j 行向下找一个最小的 p ，满足 a[p][i]=1。这里的最小的就已经满足题目要求了，不必要在二分了。也就是说，每次 swap 时取一个 \max 即可。

其他就跟高斯消元一模一样了。

Code

#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;
}