BZOJ 1923 外星千足虫

发表于 | 更新于

Link

一看到奇偶性，立刻想到了2-SAT。发现2-SAT要建出图枚举出各种情况的复杂度好象是指数级别。想了会儿，没办法，看题解，发现居然是这种神奇的东西。

Solution

给定mm个形如 的方程，问最少要到用到前几个方程就能判断出每个量的奇偶性。 这个转化技巧要记得 。很好理解，有奇数个奇数和就是奇数，否则和就是偶数。这道题到这就可以解决了。在Gauss-Jordan的时候，依次解每个变量，记录向下找找到Aj,i==1A_{j,i}==1的最大的jj就是答案了。

Tips

奇偶→\rightarrow2-SAT/XOR方程组。 以下纯属一个蒟蒻的自言自语 其实部分2-SAT问题也可以用XOR方程组解的？True\False对应奇偶？但应该应用范围很小吧

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::bitset;
const int N=1000+1,MAXN=N+10,MAXM=2000+10;
bitset<N> a[MAXM];
int Gauss(int n,int m)
{
	int res=0;
	for(int i=1;i<=n;i++)
	{
		
		for(int j=i;j<=m;j++)
		{
			if(a[j][i])
			{
				swap(a[i],a[j]),chkmx(res,j);
				break;
			}
			else if(j==m) return -1;
		}
		for(int j=1;j<=m;j++)
			if(a[j][i] && j!=i) a[j]^=a[i];
	}
	return res;
}
int main()
{
	freopen("input","r",stdin);
	static char s[MAXN];
	int n,m;get(n),get(m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		for(char *ptr=s;*ptr;++ptr)
			a[i][ptr-s+1]=*ptr-'0';
		scanf("%s",s);
		a[i][0]=*s-'0';
	}
	int ANS=Gauss(n,m);
	if(~ANS)
	{
		printf("%d\n",ANS);
		for(int i=1;i<=n;i++)
			puts(a[i][0]?"?y7M#":"Earth");
	}
	else puts("Cannot Determine");
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */