P3631 方格染色-隐晦的并查集
题意
给定部分方块权值（0/1），求将 2*2 的方块内填充（0/1），使权值和为奇数的方案数。
思路
我打了两种暴力，但都是在一些点上输出了0，莫名其妙。
手玩了一会会发现：
当 x 和 y 中有任意一个数字为奇数，则：
\[(x,y) \oplus (x,1) \oplus (1,y) \oplus (1,1)=0
\]
否则，我们有：
\[(x,y) \oplus (x,1) \oplus (1,y) \oplus (1,1)=1
\]
这样子我们就可以通过假定（1，1）的权值为，然后通过给出的方块权值，来限制（x，1）和（1，y）的关系，由于一个块（确定一个可以确定全部）可以有*2的贡献，所以我们考虑用并查集维护由于有两种状态，所以用扩展域并查集维护。
细节：
- 扩展域并查集有镜像关系，最后统计的数量要除以2。
思路2
使用带权并查集来维护块内的关系，即默认块内根为0，后面加入的块要满足和父节点（x,1 和 y,1）的公式，也就是说合并的时候要修改这个权值，在查询的时候要修正权值满足块内的关系。另外对于x，y为偶数的情况，可以直接修改其权值。对于将1，1的c，从0，变成1的时候等价于全部点异或1
code - 中道崩殂
点击展开
// 中道崩殂
// 什么时候看到可以自己再实现一下，主要的问题是由于 1，1 的状态是假定的，所以计数时不应统计和 1，1 连接的块
// 同时要注意扩展域并查集的范围关系
// 可能还有其他问题
// 所以看这个吧
方格染色
code2
/// copy from wlc
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn=2e5+10;
constexpr int mod=1e9;
int fa[maxn],g[maxn];//g：与父节点的异或关系
int n,m,k;
int ans;
int flag[2]= {1,1};//（1，1）为i是否有可能
int x[maxn],y[maxn],c[maxn];
void init()
{for(int i=1; i<=n+m; ++i)//1~n：第一行，第i列，n+1~m:第i行，第1列{fa[i]=i;g[i]=0;}
}
int fr(int x)
{if(x==fa[x]){return x;}int tmp=fr(fa[x]);//找根节点g[x]^=g[fa[x]]; //x与父节点的异或关系return fa[x]=tmp; //返回根节点
}
void join(int x,int y,int tmp)
{fa[x]=y;g[x]=tmp;//x，y的异或关系
}
int solve()
{init();fa[n+1]=1;//第1列第1行=第1列第1行for(int i=1; i<=k; ++i){int xr=fr(x[i]),yr=fr(y[i]+n);//找行变量和列变量的根节点int tmp=g[x[i]]^g[y[i]+n]^c[i];//计算两个节点应有的异或关系if(xr!=yr)//不同集合，合并它们{join(xr,yr,tmp);}else if(tmp)//同一集合但关系不满足{return 0;}}int res=-1;for(int i=1; i<=n+m; ++i){if(fa[i]==i)//找根节点{if(res==-1){res=1;//第一个连通块}else{res<<=1;//每多一个连通块,方案数×2res%=mod;}}}return res;
}
signed main()
{scanf("%lld%lld%lld",&n,&m,&k);for(int i=1; i<=k; ++i){scanf("%lld%lld%lld",x+i,y+i,c+i);if(x[i]==1&&y[i]==1)//处理(1,1)格子{flag[c[i]^1]=0;//相反颜色不可能--k;//减少总约束数--i;//在循环中回退下标//(1,1) 的约束已经通过 flag 数组处理了，不需要再作为普通约束加入并查集}else if(x[i]%2==0&&y[i]%2==0){c[i]^=1;}}if(flag[0])//(1,1)=0的情况{ans+=solve();}if(flag[1])//(1,1)=1的情况{//fa[n+1]=1暗含了c(1,1)=0，只要把整个图翻转过来，//我们就把(1，1)=1变为(1,1)=0，如果本来满足在每个2*2区域内红色个数为奇数，那么翻转过来也为奇数for(int i=1; i<=k; ++i){if(x[i]>1&&y[i]>1){c[i]^=1;}}ans+=solve();}ans%=mod;printf("%lld\n",ans);return 0;
}