BZOJ2303 APIO2011方格染色
2024-09-22 02:32:42
这题太神了
首先我们可以发现只有当i和j都是偶数时a[1][1]^a[1][j]^a[i][1]^a[i][j]=1才满足情况,其它时都为0
所以我们可以先把i和j都为偶数的地方^1变为0
下面才是最牛逼的地方,并查集的应用在这里体现的淋漓尽致。
0表示相同 1表示不同
一开始赋初值都表示为相同
然后每次更新并查集时只要更新他到根所有的数异或起来就是他与根的关系
由于根的g一定为0,所以此时得到的还有它实际应该是多少
我们假设一种比较复杂的情况
我们只有a[1][j]^a[i][1]^a[i][j]=0才成立!
假设此时a[i][j]的值为1(题目给出)
所以当且仅当a[1][j]与a[i][1]颜色不同时才成立
假设此时i到根异或起来为1,j到根异或起来为0
也就是说i与根颜色不同,j与根颜色相同
那么我们把两根合并时两根关系应该是什么?
相同对不对!
我们又发现此时分于两树时a[1][j]^a[i][1]^a[i][j]也为0(1^0^1=0)
结果一样对不对!
仔细想想其实他是因为异或满足的三角关系
于是乎很轻松的解决了
By:大奕哥
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+,mod=1e9;
typedef long long ll;
struct node{
int x,y,z;
}a[N];
int n,m,k,fa[N],g[N];
int get(int x)
{
if(x==fa[x])return x;
int t=get(fa[x]);
g[x]^=g[fa[x]];
return fa[x]=t;
}
ll calc()
{
for(int i=;i<=m+n;++i)fa[i]=i=i,g[i]=;
fa[+n]=;
for(int i=;i<=k;++i)
{
int fx=get(a[i].x),fy=get(a[i].y+n);
int tmp=g[a[i].x]^g[a[i].y+n]^a[i].z;
if(fx!=fy){
g[fx]=tmp;fa[fx]=fy;
}
else if(tmp)return ;
}
int ans=;
for(int i=;i<=n+m;++i)
{
if(get(i)==i)
{
if(ans==)ans=;
else
{
ans<<=;ans%=mod;
}
}
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int flag=-;
for(int i=;i<=k;++i)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
if(a[i].x+a[i].y==){flag=a[i].z,k--,i--;continue;}
if(!((a[i].x|a[i].y)&))a[i].z^=;
}
ll ans=;
if(flag==-||flag==)ans=calc();
if(flag==-||flag==){
for(int i=;i<=k;++i)
if(a[i].x>&&a[i].y>)
a[i].z^=;
ans+=calc();
}
ans%=mod;
printf("%lld\n",ans);
return ;
}
最新文章
- bzoj1051Tarjan裸题
- .net 4.0 ValidateRequest=";false"; 无效
- 【wikioi】1040 统计单词个数
- MYSQL 基于GTID的复制
- Elasticsearch分布式搜索集群配置
- js判断手机连接网络类型
- perl学习笔记(3)—— 坑
- python学习笔记--Django入门四 管理站点
- RabbitMQ 笔记-基本概念
- git修改远程仓库地址
- 设置TabWidget的样式的方法、关联Fragment与tabwidget的方法、点击tab显示相应Fragment方法
- python——函数之生成器
- ubantu下Navicat乱码的问题
- gym-101350M
- Vue(五) 购物车案例
- linux下php命令无法使用如何解决
- cordova性能优化方法
- vetur插件提示 [vue-language-server] Elements in iteration expect to have &#39;v-bind:key&#39; directives
- asp.net mvc中的用户登录验证过滤器
- Android图片编码机制深度解析(Bitmap,Skia,libJpeg)