[BZOJ1923/Luogu2447][SDOI2010]外星千足虫 (高斯消元)

发布于 2018-03-29  68 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1923/Luogu2447][SDOI2010]外星千足虫 (高斯消元)

Description

BZOJ1923

Tag

高斯消元

解决思路

地球上的虫子足的奇偶性为0,外星的为1,那么题目就是给出若干个异或方程,求解。
直接高斯消元。注意判断多解的情况。另外,要记录最近的能够出解的地方。
由于只有异或操作,所以可以用bitset优化。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=2010;
const int inf=2147483647;

int n,m;
int Ans=0;
bitset<maxN> A[maxN];
char Input[maxN];

void Gauss();

int main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>(Input+1);
        for (int j=1;j<=n;j++) A[i][j]=Input[j]-'0';
        int x;cin>>x;
        A[i][n+1]=x;
    }
    Gauss();
    if (Ans==-1){
        cout<<"Cannot Determine"<<endl;
        return 0;
    }
    cout<<Ans<<endl;
    for (int i=1;i<=n;i++)
        if (A[i][n+1]) cout<<"?y7M#"<<endl;
        else cout<<"Earth"<<endl;
    return 0;
}

void Gauss()
{
    int now=0;
    for (int i=1;i<=n;i++)
    {
        int j=now+1;
        while ((A[j][i]==0)&&(j<=m)) j++;
        if (j==m+1){//多解
            Ans=-1;break;
        }
        now++;if (now!=j) swap(A[now],A[j]);
        Ans=max(Ans,j);//记录能得到解的最早的地方
        for (int k=1;k<=m;k++)
            if ((k!=now)&&(A[k][i]==1)) A[k]^=A[now];
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1923/Luogu2447][SDOI2010]外星千足虫 (高斯消元)


HNCJ OIer