「BZOJ2303」[Apio2011] 方格染色
Description
Sam和他的妹妹Sara有一个包含n × m个方格的
表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好，他们想要表格中每个2 × 2的方形区
域都包含奇数个（1 个或 3 个）红色方格。例如，右
图是一个合法的表格染色方案（在打印稿中，深色代
表蓝色，浅色代表红色） 。
可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara
非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格
仍然满足她们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？
Input
输入的第一行包含三个整数n, m和k，分别代表表格的行数、列数和已被染
色的方格数目。
之后的k行描述已被染色的方格。其中第 i行包含三个整数xi, yi和ci，分别
代表第 i 个已被染色的方格的行编号、列编号和颜色。ci为 1 表示方格被染成红
色，ci为 0表示方格被染成蓝色。
Output
输出一个整数，表示可能的染色方案数目 W 模 10^9得到的值。（也就是说，如果 W大于等于10^9，则输出 W被10^9除所得的余数）。
对于所有的测试数据，2 ≤ n, m ≤ 106
，0 ≤ k ≤ 10^6
，1 ≤ xi ≤ n，1 ≤ yi ≤ m。
Sample Input
2 2 1
1 2 0
2 3 1
Sample Output
HINT
数据为国内数据+国际数据+修正版
鸣谢GYZ
题解
如果确定了第一行，接下来的每一行只会是
变换1.上一行所有奇数列异或1后得到
变换2.上一列所有偶数列异或1后得到
如果没有矛盾，显然答案就是第一行的方案数 * 2^（2到n行空行数）
发现如果同一行的两列若都染色，则这两列的颜色是相互约束的
用个并查集，把同一行的所有列并起来，第一行方案数即确定连通块颜色的方案数
考虑第一行已染色的情况，某连通块某列在第一行已染色，则该连通块颜色确定
最终第一行染色方案为2^（未确定颜色的连通块个数）
判断无解的情况
给定某一行的两列a，b颜色ca，cb，我们就可以得出第一行这两列同色（0）or反色（1）
1.奇偶性相同的列（a mod 2 = b mod 2），第一行a，b列颜色关系为ca ^ cb
2.奇偶性相同的列（a mod 2 <> b mod 2），设第一行到此行进行p1次变换1，p2次变换2
则p1+p2=行号-1
第一行a，b列颜色关系为cx^cy^（行号-1）
用一个并查集判矛盾
只计算方案
|
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 56 57 58 59 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K,tot; int fa[1000005]; bool mark[1000005],vis[1000005]; vector<int> r[1000005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int qpow(ll a,ll b) { ll ans=1; for(int i=b;i;i>>=1,a=(a*a)%mod) if(i&1)ans=(ans*a)%mod; return ans; } int main() { n=read();m=read();K=read(); for(int i=1;i<=m;i++)fa[i]=i; for(int i=1;i<=K;i++) { int a=read(),b=read(),c=read(); if(a==1)vis[b]=1; else mark[a]=1,r[a].push_back(b); } for(int i=2;i<=n;i++) for(int j=1;j<r[i].size();j++) { int p=find(r[i][j]),q=find(r[i][j-1]); fa[p]=q; if(vis[p])vis[q]=1; } for(int i=1;i<=m;i++)if(fa[i]==i&&!vis[i])tot++; for(int i=2;i<=n;i++)if(!mark[i])tot++; printf("%d\n",qpow(2,tot)); return 0; } |
AC
|
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K,tot; int fa[1000005],F[1000005],c[1000005]; bool mark[1000005],vis[1000005]; vector<int> r[1000005],col[1000005]; int qpow(ll a,ll b) { ll ans=1; for(int i=b;i;i>>=1,a=(a*a)%mod) if(i&1)ans=(ans*a)%mod; return ans; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int find2(int x) { if(x==F[x])return x; int tmp=find2(F[x]); c[x]^=c[F[x]]; return F[x]=tmp; } bool add(int a,int b,int f) { int p=find2(a),q=find2(b); if(p==q) return (c[a]^c[b])==f; else { F[p]=q; c[p]=(c[a]^c[b]^f); return 1; } } int main() { n=read();m=read();K=read(); for(int i=1;i<=m;i++)fa[i]=i,F[i]=i; for(int i=1;i<=K;i++) { int a=read(),b=read(),c=read(); if(a==1)vis[b]=1; mark[a]=1; r[a].push_back(b); col[a].push_back(c); } for(int i=1;i<=n;i++) for(int j=1;j<r[i].size();j++) { int x=r[i][j],y=r[i][j-1],cx=col[i][j],cy=col[i][j-1]; int p=find(x),q=find(y); fa[p]=q; if(vis[p])vis[q]=1; int t=cx^cy; if(x%2!=y%2)t=(t^(i-1))&1; if(!add(x,y,t)){puts("0");return 0;} } for(int i=1;i<=m;i++)if(fa[i]==i&&vis[i]==0)tot++; for(int i=2;i<=n;i++)if(!mark[i])tot++; printf("%d\n",qpow(2,tot)); return 0; } |
OI 课件=>
