Luogu2447/BZOJ1923 [SDOI2010]外星千足虫

题目传送门

算法分析

不难看出这相当于是解\(n\)元一次异或方程组，类比\(n\)元一次方程组的解法，不难想到使用高斯消元。

发现数据范围比较大，\(n^3\)是肯定过不去的，因此想到01矩阵用bitset存储，用bitset Xor运算实现对其他方程的转化，时间复杂度\(\frac{n^3}{32}\)可以通过。

求最早确定结果的时间，只需要再记录一个\(id[i]\)表示当前第\(i\)个方程是输入的第\(id[i]\)个方程，对每一次使用的方程的\(id\)取最大值即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
#define maxm 2005
template<typename Tp>
void read(Tp &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){f=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
int n,m;
bitset<maxn>a[maxm];
int id[maxm],ans;
int main(){
    read(n);read(m);int x;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n+1;j++){
            scanf("%1d",&x);
            a[i][j]=x;
        }
        id[i]=i;
    }
    for(int i=1;i<=n;i++){
        int p=i;
        while(!a[p][i]&&p<=m)p++;
        ans=max(ans,id[p]);
        if(p==m+1){
            puts("Cannot Determine");
            return 0;
        }
        if(i!=p){
            swap(a[i],a[p]);swap(id[i],id[p]);
        }
        for(int j=1;j<=m;j++){
            if(i==j)continue;
            if(a[j][i])a[j]=a[j]^a[i];
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i++){
        puts(a[i][n+1]?"?y7M#":"Earth");
    }
    return 0;
}

Luogu2447/BZOJ1923 [SDOI2010]外星千足虫

原文：https://www.cnblogs.com/ZigZagKmp/p/11491105.html