【P2447 [SDOI2010]外星千足虫】 题解

题目链接:https://www.luogu.org/problemnew/show/P2447

dalao们都说简单…解异或方程组

可我不是dalao qwq

 #include <algorithm>
 #include <cstdio>
 #include <cmath>
 #include <iostream>
 #include <bitset>
 using namespace std;
 const int maxn = ;
 const double eps = 1e-;
 char s[maxn];
 bitset<maxn> A[maxn];
 int n, m, ans[maxn], flag;
 bool check;
 int main()
 {
     scanf("%d%d",&n,&m);
     for(int i = ; i <= m; i++)
     {
         scanf("%s",s+);
         for(int j = ; j <= n; j++)
         A[i][j] = s[j]-'';
         int p;
         scanf("%d",&p);
         A[i][n+] = p;
     }
     for(int i = ; i <= n; i++)
     {
         int p = i;
         while(p < m+ && !A[p][i]) p++;
         if(p == m+)
         {
             printf("Cannot Determine\n");
             return ;
         }
         else flag = max(flag, p);
         if(i != p) swap(A[i],A[p]);
         for(int j = i + ; j <= m; j++)
         if(A[j][i]) A[j]^=A[i];
     }
     ans[n] = A[n][n+];
     for(int i = n - ; i >= ; i--)
     {
         ans[i] = A[i][n+];
         for(int j = i + ; j <= n; j++)
             ans[i] ^= ans[j] * A[i][j];
     }
     printf("%d\n",flag);
     for(int i = ; i <= n; i++)
     {
         if(ans[i] == ) printf("Earth\n");
         if(ans[i] == ) printf("?y7M#\n");
     }
     return ;
 }