BZOJ2303/APIO2011/方格染色

Posted on By 二价氢

#题目描述

Sam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好,他们想要表格中每个2×2的方形区 域都包含奇数个(1个或3个)红色方格。 可是昨天晚上,有人已经给表格中的一些方格染上了颜色!现在Sam和Sara非常生气。不过,他们想要知道是否可能给剩下的方格染上颜色,使得整个表格仍然满足她们的要求。如果可能的话,满足他们要求的染色方案数有多少呢?

#做法

见代码下注释

#复杂度分析 其中每个点访问一次,利用平衡树,每次压入、查询前驱、查询后继、删除操作都是

#AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxk=100005,maxn=200005,mod=1000000000;
int n,m,k;
int q[maxk][3];
int si11;
int gr[maxn],si[maxn];
int ex;
int find(int e,int &s)
{
	if (gr[e]<=0)
	{
		s=0;
		return e;
	}
	gr[e]=find(gr[e],s);
	si[e]^=s;
	s=si[e];
	return gr[e];
}
bool uni(int e1,int e2,int s)
{
	int s1,s2;
	int g1=find(e1,s1),g2=find(e2,s2);
	if (g1==g2)
	{
		return (s1^s2)==s;
	}
	if (gr[g1]>=gr[g2])
	{
		if (gr[g1]==gr[g2])
			gr[g2]--;
		si[g1]=(s1^s2^s);
		gr[g1]=g2;
	}else
	{
		si[g2]=(s1^s2^s);
		gr[g2]=g1;
	}
	ex--;
	return true;
}
long long Pow(long long n,long long k)
{
	long long r=1;
	for (;k;(n*=n)%=mod,k>>=1)
		if (k&1)
			(r*=n)%=mod;
	return r;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	uni(n+m+1,n+m+2,1);
	ex=n+m-1;
	for (int i=1;i<=k;i++)
	{
		scanf("%d%d%d",&q[i][0],&q[i][1],&q[i][2]);
		if (q[i][0]==1 && q[i][1]==1 && q[i][2]==1)
			si11=1;
	}
	for (int i=1;i<=k;i++)
	{
		int r=q[i][0],c=q[i][1],co=q[i][2];
		if (r==1)
		{
			if (!uni(c,n+m+1+(co^si11),0))
			{
				printf("0\n");return 0;
			}
		}else if (c==1)
		{
			if (!uni(m+r,n+m+1+(co^si11),0))
			{
				printf("0\n");return 0;
			}
		}else
		{
			int cco=!(r&1)&&!(c&1);
			if (!uni(c,m+r,co^cco^si11))
			{
				printf("0\n");return 0;
			}
		}
	}
	printf("%lld\n",Pow(2,ex));
	return 0;
}

/**************************************************************************\

  apio2011 棋盘染色
   并查集

   + . . . . | . . . .
   . . . . . v . . . .
   . . . . . ' . . . .
   ->''''''''* . . . .
   . . . . . . . . . .
   . . . . . . . . . .
   . . . . . . . . . .
   . . . . . . . . . .

   如上图,一个点(x,y)的颜色可以由(1,1)['+'],(x,1)['|'],(1,y)['-']唯一确定
   跟据题目所给的条件,我们可以确定若干对诸如“(x,1)和(1,y)必须相同”的东西
   用并查集维护它,如果遇到矛盾的信息,答案显然为0

\*************************************************************************/