LG2447/BZOJ1923 「SDOI2010」外星千足虫 高斯消元

问题描述

LG2447

BZOJ1923

题解

显然是一个高斯消元，但是求的东西比较奇怪

发现这个方程组只关心奇偶性，于是可以用一个\(\mathrm{bitset}\)进行优化，用xor来进行消元操作。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

void read(int &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') fh=-1,ch=getchar();
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

#define maxn 1007

int n;

bitset<maxn>a[maxn<<1];

int pla,ans,tmp;
int m;
int main(){
    read(n);read(m);
    for(register int i=1;i<=m;i++){
        for(register int j=1;j<=n+1;j++) scanf("%1d",&tmp),a[i][j]=tmp;
    }
    for(register int i=1;i<=n;i++){
        pla=i;
        while(pla<=m&&a[pla][i]==0) pla++;
        if(pla==m+1){
            puts("Cannot Determine");return 0;
        }
        ans=max(ans,pla);
        if(pla!=i) swap(a[pla],a[i]);
        for(register int j=1;j<=m;j++){
            if(i==j||a[j][i]==0) continue;
            a[j]=a[i] xor a[j];
        }
    }
    printf("%d\n",ans);
    for(register int i=1;i<=n;i++){
        if(a[i][n+1]&1) puts("?y7M#");
        else puts("Earth");
    }
    return 0;
}

LG2447/BZOJ1923 「SDOI2010」外星千足虫 高斯消元

原文：https://www.cnblogs.com/liubainian/p/11484570.html