[SDOI2010] 外星千足虫

高斯消元解异或方程组。

题目还是挺裸的，大概看一看就知道怎么写了吧。

解异或方程组跟解正常的方程组差不多，我发现我喜欢上那种消成对角线的方法了。

这道题数据范围1000*2000，用bitset优化一下就能过了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<bitset>
 5 using std::bitset;
 6 using std::max;
 7 typedef bitset<1005> bs;
 8 
 9 int n,m;
10 bs a[2005];
11 
12 void swap(bs &q,bs &w)
13 {
14     bs t=q;q=w;w=t;
15 }
16 
17 int main()
18 {
19     scanf("%d%d",&n,&m);
20     for(int i=1;i<=m;i++)
21     {
22         char str[1005];int tmp;
23         scanf("%s",str+1);
24         for(int j=1;j<=n;j++)
25             if(str[j]=='1')a[i].set(j);
26         scanf("%d",&tmp);
27         if(tmp)a[i].set(n+1);
28     }
29     int ans=0;
30     for(int i=1;i<=n;i++)
31     {
32         int p=i;
33         while(p<=m&&(!a[p][i]))p++;
34         if(p==m+1)
35             return printf("Cannot Determine"),0;
36         ans=max(ans,p);
37         if(p!=i)swap(a[p],a[i]);
38         for(int j=1;j<=m;j++)
39         {
40             if((j==i)||(!a[j][i]))continue;
41             a[j]^=a[i];
42         }
43     }
44     printf("%d
",ans);
45     for(int i=1;i<=n;i++)
46     {
47         if(a[i][n+1])printf("?y7M#
");
48         else printf("Earth
");
49     }
50     return 0;
51 }

我手写swap忘加取址了，结果样例过不了，找了好长时间错都没发现......

（因为我一直盯着主函数看，没往swap那边想）