CF 461D Appleman and Complicated Task解题报告

题目


给你一个n*n网格,每一格要么是0要么是1要么为空,要求你用0或1填满所有空格,使得每个格子周围的0有偶数个。

题解

首先我们观察到这样一个事实:当第一行确定后,整个网格的填法就确定了。我们以N=8为例,把这种确定方法列出来:其中,“0246”这样的数的含义为,假设第一行为a[0..7],它表示该格的值是a[0] xor a[2] xor a[4] xor a[6].



可以发现,这个形式是很规整的。都是“246”或者“1357”这种,连续的奇/偶数。

因此,我们的问题就变成了:问有多少种a的取值,满足K组形如a[1] xor a[3] xor a[5] xor a[7] = 1(或者0)这样的限制。

不妨设a的“奇/偶前缀和”为s,就是说s[6] = a[0] xor a[2] xor a[4],s[5] = a[0] xor a[3],等等。那么a[1] xor a[3] xor a[5] xor a[7] = 1这个限制就变成了s[1] xor x[9] = 1.可以发现,所有对a的“段”限制都变成了s中某两个数的限制:它们要么相等要么相反。

这就变成了一道有成熟算法的题目:让每个s[i]都对应两个元素i和i’,二者的值相反。对于s[a] xor s[b] = 0这种限制,就把a和b,a’和b’放在同一个并查集中;对于s[a] xor s[b] = 1这种限制,就把a和b’,a’和b放在同一个并查集中。如果在某个时刻,某个a和a’被并在了一起,则无解。

设最后剩下的等价类数量是cnt,可以发现,其中有4个的值是确定的:s[0]和s[1],以及它们的反。因此,答案就是2^((cnt-4)/2).

代码

#include
#include
#include
#include
using namespace std;
const int SIZEN=100010;
const int MOD=1000000007;
int pow2(int n){
	int ans=1;
	for(int i=1;i<=n;i++){
		ans=(ans<<1)%MOD;
	}
	return ans;
}
class EQ2{//solver
public:
	int ufs[SIZEN*2];
	void clear(void){
		memset(ufs,-1,sizeof(ufs));
	}
	EQ2(){clear();}
	int grand(int x){
		return ufs[x]==-1?x:ufs[x]=grand(ufs[x]);
	}
	bool merge(int a,int b){//元素a和元素b 
		int ga=grand(a),gb=grand(b);
		if(grand(a^1)==gb) return false;
		if(grand(b^1)==ga) return false;
		if(ga!=gb) ufs[ga]=gb;
		return true;
	}
	bool test(int a,int b,int t){//变量a和变量b的xor是t 
		if(t==0){
			return merge(2*a,2*b)&&merge(2*a+1,2*b+1);
		}
		else if(t==1){
			return merge(2*a,2*b+1)&&merge(2*a+1,2*b);
		}
	}
	int count(int N){//0~N
		N=2*N+1;
		int ans=0;
		for(int i=0;i<=N;i++){
			if(grand(i)==i) ans++;
		}
		return ans;
	}
}S;
void work(void){
	int N,K,a,b,p;
	char ch[10];
	scanf("%d%d",&N,&K);
	for(int i=1;i<=K;i++){
		scanf("%d%d",&a,&b);
		a--,b--;
		scanf("%s",ch);
		p=(ch[0]=='x'?0:1);
		int l=abs(a-b);
		int r=min(a+b,2*(N-1)-(a+b));
		if(!S.test(l,r+2,p)){
			printf("0\n");
			return;
		}
	}
	int cnt=S.count(N+1);
	printf("%d\n",pow2((cnt-4)/2));
}
int main(){
	//freopen("input.in","r",stdin);
	work();
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注