bzoj 2303: [Apio2011]方格染色

Description

Sam和他的妹妹Sara有一个包含n × m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好，他们想要表格中每个2 × 2的方形区域都包含奇数个（1 个或 3 个）红色方格。例如，右图是一个合法的表格染色方案（在打印稿中，深色代表蓝色，浅色代表红色）。
可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？

Input

输入的第一行包含三个整数n, m和k，分别代表表格的行数、列数和已被染色的方格数目。
之后的k行描述已被染色的方格。其中第 i行包含三个整数$x_{i}$, $y_{i}$和$c_{i}$，分别代表第 i 个已被染色的方格的行编号、列编号和颜色。$c_{i}$为 1 表示方格被染成红色，$c_{i}$为 0表示方格被染成蓝色。

Output

输出一个整数，表示可能的染色方案数目 W 模 10^9得到的值。（也就是说，如果 W大于等于10^9，则输出 W被10^9除所得的余数）。

对于所有的测试数据，$2 ≤ n, m ≤ 10^6，0 ≤ k ≤ 10^6，1 ≤ x_{i} ≤ n，1 ≤ y_{i} ≤ m$。

窝是不会做去看题解的哇……

空灰冰魂这位大佬讲得比较清晰。

思路大约是确定第一行第一列以后其他点都可以确定。

然后对于一组

$$a_{x,y}⊕a_{x-1,y}⊕a_{x,y-1}⊕a_{x-1,y-1}=1$$

它可以化成$$a_{x,y}⊕a_{1,y}⊕a_{x,1}⊕a_{1,1}=f(x,y)$$

f(x,y)=(x&1)|(y&1)

如果有修改在第一行第一列的，我先跑一遍bfs全染出来，再并查集处理那些等于和不等关系。

#include<set>

#include<cstdio>

#include<algorithm>

#define S (!((p[i].x|p[i].y)&1))

#define MN 2100000

using namespace std;

int read_p,read_ca,read_f;

inline int read(){

    read_p=;read_ca=getchar();read_f=;

    while(read_ca<''||read_ca>'') read_f=read_ca=='-'?-:read_f,read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p*read_f;

}

struct bi{int y,z,ne;}b[MN];

struct na{int x,y,c;}p[MN];

const int MOD=1e9;

int n,m,k,MMH=,C[MN],fa[MN],w[MN],l[MN],num;

bool v[MN],gg;

inline void in(int x,int y,int z){b[++num].y=y;b[num].z=z;b[num].ne=l[x];l[x]=num;}

inline void dfs(int x,int c){

    if (C[x]!=c&&C[x]!=-) gg=;

    if (v[x]) return;

    v[x]=;C[x]=c;

    for (int i=l[x];i;i=b[i].ne) dfs(b[i].y,c^b[i].z);

}

int gf(int x){

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

    int f=fa[x];fa[x]=gf(fa[x]);w[x]^=w[f];

    return fa[x];

}

inline void add(int x,int y,int c){

    int X=gf(x),Y=gf(y);

    if (X==Y){

        if (w[x]^w[y]^c) gg=;

    }else fa[X]=Y,w[X]=c^w[x]^w[y];

    //printf("%d %d %d %d %d %d %d %d\n",x,y,w[x],w[y],X,Y,c,gg);

}

inline void work(int x){

    num=;gg=;

    for (int i=;i<=n+m-;i++) C[i]=-,fa[i]=i,l[i]=v[i]=,w[i]=;

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

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

    else if (p[i].x==){if (C[p[i].y]==(p[i].c^))gg=;C[p[i].y]=p[i].c;}

    else if (p[i].y==){if (C[p[i].x-+m]==(p[i].c^))gg=;C[p[i].x-+m]=p[i].c;}

    else in(p[i].y,p[i].x-+m,p[i].c^x^S),in(p[i].x-+m,p[i].y,p[i].c^x^S);

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

    if (C[i]!=-&&!v[i]) dfs(i,C[i]);

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

    if (p[i].x!=&&p[i].y!=) add(p[i].y,p[i].x-+m,p[i].c^x^S)/*,printf("%d %d %d\n",p[i].y,p[i].x-1+m,p[i].c^x^S)*/;

    if (gg) return;

    int mmh=;

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

    if (C[i]==-&&fa[i]==i) mmh+=mmh,mmh-=mmh>=MOD?MOD:;

    MMH+=mmh;MMH-=MMH>=MOD?MOD:;

    //printf("%d %d\n",x,mmh);

}

int main(){

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

    for (int i=;i<=k;i++) p[i].x=read(),p[i].y=read(),p[i].c=read();

    work();work();

    printf("%d\n",MMH);

}

巴特西

bzoj 2303: [Apio2011]方格染色

Description

Input

Output

最新文章

热门文章