首页 > 代码库 > BZOJ 2303: [Apio2011]方格染色 题解
BZOJ 2303: [Apio2011]方格染色 题解
题目大意：
有n*m的方格，中间的数要么是1，要么是0，要求任意2*2的方格中的数异或和为1。已知一部分格子中的数，求合法的填数的方案数。
思路：
由题意得：a[i][j]^a[i][j+1]^a[i+1][j]^a[i+1][j+1]=1，令这个式子为S(i,j)，那么对于某一格(i,j)，我们把S(1,1)...S(i,j)异或起来，则可得当i,j均为偶数时a[1][1]^a[i][1]^a[1][j]^a[i][j]=1（于是为了方便先预处理一下），否则a[1][1]^a[i][1]^a[1][j]^a[i][j]=0。可以枚举a[1][1]的值再由a[i][j]得到a[i][1]与a[1][j]的相同情况（可默认所有数均为0），于是相同就用并查集并起来。若有(n+1)个联通块则有$2^n$种方案（因为与a[1][1]相同的已经确定了）。
代码：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 const int M=2000009,mo=1000000000; 5 int n,m,i,k,sum,u,v,t,ans,x[M],y[M],z[M],g[M],fa[M]; 6 7 int read() 8 { 9 int x=0;10 char ch=getchar();11 while (ch<‘0‘ || ch>‘9‘) ch=getchar();12 while (ch>=‘0‘ && ch<=‘9‘) x=(x<<1)+(x<<3)+ch-48,ch=getchar();13 return x;14 }15 16 int getfa(int x)17 {18 if (x==fa[x]) return x;19 int t=getfa(fa[x]); g[x]^=g[fa[x]];20 return fa[x]=t;21 }22 23 int wk()24 {25 for (i=1;i<=n+m;i++) fa[i]=i,g[i]=0;26 for (fa[n+1]=i=1;i<=k;i++)27 {28 u=getfa(x[i]),v=getfa(y[i]+n),t=g[x[i]]^g[y[i]+n]^z[i];29 if (u!=v) fa[u]=v,g[u]=t;30 else if (t) return 0;31 }32 for (sum=-1,i=1;i<=n+m;i++)33 if (getfa(i)==i)34 if (sum==-1) sum=1;35 else if ((sum<<=1)>=mo) sum-=mo;36 return sum;37 }38 39 int main()40 {41 bool flag[2]={1,1};42 n=read(),m=read(),k=read();43 for (i=1;i<=k;i++)44 {45 x[i]=read(),y[i]=read(),z[i]=read();46 if (x[i]+y[i]==2) { flag[z[i]]=0,i--,k--; continue; }47 if (!((x[i]|y[i])&1)) z[i]^=1;48 }49 if (flag[1]) ans=wk();50 if (flag[0])51 {52 for (i=1;i<=k;i++)53 if (x[i]>1 && y[i]>1) z[i]^=1;54 if ((ans+=wk())>=mo) ans-=mo;55 }56 printf("%d\n",ans);57 return 0;58 }
BZOJ 2303: [Apio2011]方格染色 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。