BZOJ 1923: [Sdoi2010]外星千足虫

Description

给出几个异或方程组求解,\(n \leqslant 2000\)

Sol

高斯消元.

直接消元就行,遇到自由元就直接输出,同时记录一下用到的最高行数.

复杂度不科学就可以用 bitset 啊...跑的灰常快...不过他没有重载某一位的异或操作,需要人工判断一下.

Code

/**************************************************************

    Problem: 1923

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:336 ms

    Memory:1784 kb

****************************************************************/

#include <cstdio>

#include <cstring>

#include <bitset>

#include <iostream>

using namespace std;

const int N = 2005;

int n,m,ans;

bitset< N > a[N];

/*

void print(){

    for(int i=0;i<m;i++) cout<<a[i]<<endl;

    cout<<"-------------------------------"<<endl;

}*/

int gauss(){

    for(int i=0,r,j;i<n;i++){

        for(r=-1,j=i;j<m;j++) if(a[j][i]){ r=j;break; }

//      cout<<r<<endl;

//      print();

        if(r==-1){ puts("Cannot Determine");return 0; }

        if(r!=i) swap(a[i],a[r]);

        ans=max(ans,r);

        for(j=i+1;j<m;j++) if(a[j][i]) a[j]^=a[i];

    }

    for(int i=n-1;~i;i--){

        for(int j=i+1;j<n;j++) if(a[j][n]*a[i][j]){

            if(a[i][n]) a[i][n]=0;else a[i][n]=1;

        }

    }return 1;

}

void out(){

    cout<<ans+1<<endl;

    for(int i=0;i<n;i++) if(a[i][n]) puts("?y7M#");else puts("Earth");

}

int main(){

//  freopen("in.in","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++){

        char s[N];int x;

        memset(s,0,sizeof(s));

        scanf("%s",s);

        for(int j=0;j<n;j++) a[i][j]=s[j]-'0';

        scanf("%d",&x);

        a[i][n]=x;

    }

    if(gauss()) out();

    return 0;

}