Vexoben
Jun 20, 2018
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2303
题意
Sam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。 出于个人喜好，他们想要表格中每个2×2的方形区域都包含奇数个（1个或3个）红色方格。 可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？
题解
不会带权并查集……直接戳中知识盲点。
首先发现，如果第一行和第一列都已经确定，整个矩形就唯一确定了。
对于一组限制(x,y)颜色是c,将所有右下角在[2…x],[2…y]的方形异或起来得到：
a[1][1]^a[1][y]^a[x][1]^a[x][y]=[x,y不同时为奇数]
如果枚举出a[1][1]，再加上题目给出的a[x][y]，就可以推出a[1][y]和a[x][1]的关系。
维护这个关系，考虑使用一个带权并查集。并查集中除了记录fa外，还记录a[x]^a[fa[x]]，路径压缩之后就变成了x与所在并查集根节点的关系。
这样很容易判断无解的情况。如果有解，且并查集的个数是cnt个，那么答案是2^(cnt-1)，这是因为除了a[1][1]所在的并查集只能使用枚举的那个颜色外，别的并查集都可以有两种选择。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+10;
const int mod=1e9;
int n,m,k;
int x[N],y[N],z[N];
int fa[N*2],col[N*2];
inline int Find(int x) {
if (fa[x]==x) return x;
int t=Find(fa[x]);
col[x]^=col[fa[x]];
return fa[x]=t;
}
int calc() {
for (int i=1;i<=n+m;i++) fa[i]=i,col[i]=0;
fa[m+1]=1;
for (int i=1;i<=k;i++) {
int u=Find(x[i]+m),v=Find(y[i]),t=col[x[i]+m]^col[y[i]]^z[i];
if (u==v) {
if (t) return 0;
continue;
}
col[u]=t; fa[u]=v;
}
int ans=0;
for (int i=1;i<=n+m;i++) {
if (Find(i)==i) {
if (!ans) ans=1;
else ans=ans*2%mod;
}
}
return ans;
}
int main() {
scanf("%d%d%d",&n,&m,&k);
int f=-1;
for (int i=1;i<=k;i++) {
scanf("%d%d%d",&x[i],&y[i],&z[i]);
if (x[i]+y[i]==2) f=z[i],i--,k--;
else if ((x[i]|y[i])%2==0) z[i]^=1;
}
int ans1=0,ans2=0;
if (f!=1) ans1=calc();
if (f!=0) {
for (int i=1;i<=k;i++) {
if (x[i]>1&&y[i]>1) z[i]^=1;
}
ans2=calc();
}
printf("%d",(ans1+ans2)%mod);
return 0;
}