bzoj1923,戳我戳我

Solution:

• 这个高斯消元/线性基很好看出来，主要是判断在第K 次统计结束后就可以确定唯一解的地方和\(bitset\)的骚操作
• （我用的线性基）判断位置，我们可以每次加入一个线性基时判断是不是全被异或掉了，如果没有，说明这个方程不是冗余的，那么我们可记录非冗余方程个数
• 如果非冗余方程个数小于\(n\)，那就是个不定方程组，有无数种解，否则，在个数第一次达到\(n\)时，就可输出当时输入方程的号码
• 还有一个点就是压空间与时间，这题主要是时间，用到大杀器\(bitset\)，具体看我，这位辽宁省队巨佬的博客吧

Code:

//It is coded by Ning_Mew on 5.29

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+7,maxm=2e3+7;

int n,m;

int ans[maxn],tot=0;

bitset<maxn>x[maxn];

string s;

bool pr;

void push(bitset<maxn>S){

  for(int i=n-1;i>=0;i--){

    if(S[i]){

      if(x[i][i]){S=(S^x[i]);}

      else {x[i]=S;tot++;return;}

    }

  }

}

int main(){

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

  if(m<n){printf("Cannot Determine\n");return 0;}

  pr=false;

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

    cin>>s; bitset<maxn>S(s);

    cin>>s; if(s[0]=='1')S.flip(n);

    //cout<<i<<":"<<S[0]<<' '<<S[1]<<' '<<S[2]<<' '<<S[3]<<endl;

    push(S);if(tot==n&&!pr)pr=true,printf("%d\n",i);

  }

  if(tot<n){printf("Cannot Determine\n");return 0;}

  for(int i=n-1;i>=0;i--){

    for(int j=i-1;j>=0;j--){

      if(x[i][j]){x[i]=(x[i]^x[j]);}

    }

    if(x[i][n])printf("?y7M#\n");

    else printf("Earth\n");

  }

  return 0;

}

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会终生找不到妹子！！！