题解 [APIO2011]方格染色

xiaolilsq · 2020-02-01 21:04:55 · 题解

题目链接

刚刚做了这道题，感觉这题有诸多细节（调了我几个小时），后来发现大家的代码太麻烦了，于是过来写（shui）篇题解。

这道题思路大致是这样的（记(x,y)表示格子(x,y)的颜色）：

令x=x-1，有：

两式异或起来得到：

于是便有：

令y=y-1，得到：

两式异或起来得到：

同理：

同理亦有：

于是我们便得到若x,y中至少有一个是奇数时:

当x,y都是偶数时，自己推一下不难得到:

这时有些题解的做法是枚举(1,1)的所有可能（即0或1），其实这样做麻烦了，我们可以多开一行一列（即(0,y)和(x,0)），然后默认(0,0)=0,(1,0)=0，这样整个图就是新开的这一行这一列决定的了，然后就不必考虑那么多了

对于一个新添加的颜色(x,y)=t，若x,y中至少有一个是偶数时，令：

否则令：

用种类并查集维护一下(x,0)和(0,y)之间的关系，最后记得把(1,0)去掉，然后记录一下连通块的个数cnt，最后的答案便是2^{cnt}

放上巨丑无比的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
int fa[maxn<<2],opp[maxn<<2],del[maxn<<2];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int push(int x,int y){
    fa[x]=y;
}
int push(int x,int y,int c){
    if(c){
        x=find(x);y=find(y);
        if(x==y)return false;
        if(x==opp[y])return true;
        push(x,opp[y]);push(opp[x],y);
    }
    else{
        x=find(x);y=find(y);
        if(x==opp[y])return false;
        if(x==y)return true;
        push(x,y);push(opp[x],opp[y]);
    }
    return true;
}
long long mod=1e9;
long long power(long long a,int n){
    long long ans=1;
    while(n){
        if(n&1)ans=ans*a%mod;
        n>>=1;a=a*a%mod;
    }
    return ans;
}
int main(){
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);int all=n+m;
    for(int i=1;i<=all;++i)opp[i+all]=fa[i]=i,opp[i]=fa[i+all]=i+all;//(x,0)->x (0,y)->y+n
    int Im=0;
    for(int i=0,x,y,c,t;i<k;++i){
        scanf("%d %d %d",&x,&y,&c);
        if((x+1&1)==0&&(y+1&1)==0)c^=1;
        y+=n;
        if(!push(x,y,c)){
            Im=1;break;
        }
    }
    if(Im){
        putchar(0);
    }
    else{
        int temp=find(1),ans=0;
        del[temp]=true;del[opp[temp]]=true;
        for(int i=2;i<=all;++i){
            int x=find(i);
            if(!del[x])++ans;
            del[x]=del[opp[x]]=true;
        }
        printf("%lld",power(2,ans));
    }
    return 0;
}

似乎比其他做法要简洁吧。。。

希望这篇题解对你有帮助

欢迎提供hack数据