【bzoj 2303】【Apio2011】方格染色

題目：

http://www.lydsy.com/JudgeOnline/problem.php?id=2303

題解:

　　很神奇的思路，膜一發大佬http://www.cnblogs.com/HHshy/p/5840018.html#undefined

　　設S(i,j)=a[i][j]^a[i+1][j]^a[i][j+1]^a[i+1][j+1]。那麼将S（1,1）^S(1,2)^...^S(1,j)^S(2,1)^...^S(2,j)^.....^S(i,j)展開，對于i相同的一行（如S（1,1）^S(1,2)^...^S(1,j)），我們可以先然看出其結果為開頭的a[i][1]^a[i][j]，同時其在下一層的異或結果也是a[i+1][1]^a[i+1][j]，那麼再把每一行合并，最終我們得到此式的化簡：a[1][1]^a[i+1][1]^a[1][j+1]^a[i+1][j+1]，然後當i，j均為奇數時，我們得知a[1][1]^a[i+1][1]^a[1][j+1]^a[i+1][j+1]==1，否則為0，再把那個+1縮掉，即：（(i|j)&1）==0時，a[1][1]^a[i][1]^a[1][j]^a[i][j]==1，否則為0.設a[1][1]^a[i][1]^a[1][j]^a[i][j]為z,再移一下項，我們得到z^a[1][1]^a[i][j]==a[i][1]^a[1][j]，然後枚舉a[1][1]的值，再用并查集把有關的a[i][1]與a[1][j]連接配接起來，判斷是否會出現沖突，如果沒有沖突，我們就得到了一部分答案。最後把兩個a[1][1]值的貢獻加和即可。

1 #include<cstdio>
 2 const int N=(int )1e6+5,mod=(int) 1e9;
 3 inline int read(void ){
 4     int s=0;char ch=getchar();
 5     while(ch<'0'||ch>'9')   ch=getchar();
 6     while(ch>='0'&&ch<='9') s=s*10+(ch^48),ch=getchar();
 7     return s;
 8 }
 9 
10 int n,m,k;
11 int x[N],y[N],z[N],g[N],f[N];
12 inline int find(int x){
13     if(x==f[x]) return x;
14     int t=find(f[x]);g[x]^=g[f[x]];
15     return f[x]=t;
16 }
17 inline int solve()
18 {
19     for(int i=1;i<=n+m;i++)   f[i]=i,g[i]=0; 
20     f[n+1]=1;
21     for (int i=1;i<=k;i++)                                  
22     {                                                                                                                                               
23         int  u=find(x[i]),v=find(y[i]+n),t=g[x[i]]^g[y[i]+n]^z[i];                                               
24         if (u!=v) f[u]=v,g[u]=t;                                                                                                                             
25         else if (t) return 0;                                                                                   
26     }         
27     int sum=0;                              
28     for (int i=1;i<=n+m;i++)
29         if (f[i]==i)
30             if (!sum) sum=1;
31             else {
32                 sum<<=1;
33                 sum-=mod*(sum>mod);
34             }
35     return sum;
36 }
37 int main(){
38     bool e[2]={1,1};
39     n=read(),m=read(),k=read();
40     for(int i=1;i<=k;i++){
41         x[i]=read(),y[i]=read(),z[i]=read();
42         if(!((x[i]^1)|(y[i]^1))){
43             e[z[i]]=0,i--,k--;continue;
44         }
45         if(!((x[i]|y[i])&1))    z[i]^=1;
46     }
47     int ans=0;
48     if(e[1])    ans=solve();
49     if(e[0]){
50         for(int i=1;i<=k;i++)
51             if((x[i]^1)&&(y[i]^1)) z[i]^=1;
52         ans+=solve();
53         ans-=(ans>mod)*mod;
54     }
55     printf("%d\n",ans);
56 }      

//承認抄代碼。。

轉載于:https://www.cnblogs.com/Troywar/p/7327511.html