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 ;
}
上一篇:Problem4-Project Euler


下一篇:STM8S ADC初始化设置及应用