BZOJ 2303 方格染色

首先考虑四个格子异或值为1。

然后（重点）发现每个格子的值只和最上面，最左边，和（1,1）的格子的颜色有关。

枚举（1,1）的颜色，联立方程，可以将未知数减少，那么并查集可做。

最后算答案的时候，有些连通块颜色确定，有些不确定，不确定的*2即可。

这题要注意细节！其实一开始的思路最不好想。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 1000500

#define mod 1000000000

using namespace std;

struct pnt

{

    int x,y,c;

}p[maxn];

int n,m,k,fath[maxn<<],dis[maxn<<],val[maxn<<],flag=-,cnt[maxn<<];

void reset()

{

    for (int i=;i<=(n-)+(m-);i++)

    {

        fath[i]=i;

        dis[i]=;

        val[i]=-;

        cnt[i]=;

    }

}

int getfather(int x)

{

    if (x==fath[x]) return fath[x];

    if (val[x]!=-)

    {

        if ((val[fath[x]]!=-) && (val[fath[x]]!=(val[x]^dis[x])))

            return -;

        val[fath[x]]=val[x]^dis[x];

    }

    int ret=getfather(fath[x]);

    dis[x]^=dis[fath[x]];

    fath[x]=ret;

    return fath[x];

}

int f_pow(int a,int b)

{

    int base=a,ans=;

    while (b)

    {

        if (b&) ans=(ans*base)%mod;

        base=(base*base)%mod;

        b>>=;

    }

    return ans%mod;

}

int gets(int r)

{

    int ans=;

    if (flag==-r) return ;

    reset();

    for (int i=;i<=k;i++)

    {

        if ((p[i].x==) && (p[i].y==))

        {

            if (p[i].c!=r) return ;

        }

        else if ((p[i].x==) && (p[i].y!=)) {if ((val[n+p[i].y-]!=p[i].c) && (val[n+p[i].y-]!=-)) return ;val[n+p[i].y-]=p[i].c;}

        else if ((p[i].x!=) && (p[i].y==)) {if ((val[p[i].x-]!=p[i].c) && (val[p[i].x-]!=-)) return ;val[p[i].x-]=p[i].c;}

        else

        {

            int x=p[i].x-,y=n+p[i].y-;

            int f1=getfather(x),f2=getfather(y);

            if ((f1==-) || (f2==-)) return ;

            if (f1==f2)

            {

                int ret=dis[x]^dis[y]^r;

                if ((p[i].x%==) && (p[i].y%==)) ret^=;

                if (ret!=p[i].c) return ;

            }

            else

            {

                int ret=p[i].c^dis[x]^dis[y]^r;

                if ((p[i].x%==) && (p[i].y%==)) ret^=;

                if ((val[f1]!=-) && (val[f2]!=-))

                {

                    if ((val[f1]^ret)!=val[f2]) return ;

                }

                else if ((val[f1]==-) && (val[f2]!=-)) {fath[f1]=f2;dis[f1]=ret;}

                else if ((val[f1]!=-) && (val[f2]==-)) {fath[f1]=f2;dis[f1]=ret;val[f2]=val[f1]^ret;}

                else {fath[f1]=f2;dis[f1]=ret;}

            }

        }

    }

    for (int i=;i<=(n-)+(m-);i++)

    {

        int ret=getfather(i);

        if (ret==-) return ;

        cnt[ret]++;

    }

    for (int i=;i<=(n-)+(m-);i++)

    {

        if ((fath[i]==i) && (val[i]==-))

            ans=(ans*)%mod;

    }

    return ans%mod;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for (int i=;i<=k;i++)

    {

        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);

        if ((p[i].x==) && (p[i].y==)) flag=p[i].c;

    }

    printf("%d\n",(gets()+gets())%mod);

    return ;

}

巴特西

BZOJ 2303 方格染色

最新文章

热门文章