【题解】 bzoj1923: [Sdoi2010]外星千足虫（线性基/高斯消元）-白红宇

【题解】 bzoj1923: [Sdoi2010]外星千足虫（线性基/高斯消元）

阅读量：5099 次

发布时间：2019-06-13

本文共 1008 字，大约阅读时间需要 3 分钟。

Solution:

这个高斯消元/线性基很好看出来，主要是判断在第K 次统计结束后就可以确定唯一解的地方和\(bitset\)的骚操作

（我用的线性基）判断位置，我们可以每次加入一个线性基时判断是不是全被异或掉了，如果没有，说明这个方程不是冗余的，那么我们可记录非冗余方程个数

如果非冗余方程个数小于\(n\)，那就是个不定方程组，有无数种解，否则，在个数第一次达到\(n\)时，就可输出当时输入方程的号码

还有一个点就是压空间与时间，这题主要是时间，用到大杀器\(bitset\)，具体看，这位辽宁省队巨佬的博客吧

Code:

//It is coded by Ning_Mew on 5.29#include
    
     using namespace std;const int maxn=1e3+7,maxm=2e3+7;int n,m;int ans[maxn],tot=0;bitset
     
      x[maxn];string s;bool pr;void push(bitset
      
       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
       
        >s; bitset
        
         S(s);    cin>>s; if(s[0]=='1')S.flip(n);    //cout<
         <<":"<
          
           <<' '<
           
            <<' '<
            
             <<' '<
             
              <
              
               =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;}