[bzoj2303][Apio2011]方格染色

作者:神秘网友 发布时间:2021-11-25 14:06:41

[bzoj2303][Apio2011]方格染色

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

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\)得到的值。

Sample Input

3 4 3
2 2 1
1 2 0
2 3 1

Sample Output

8

HINT
\(2\leq n,m\leq10^6,0\leq k\leq10^6,1\leq x_i\leq n,1\leq y_i\leq m\).

Solution
设红色为1,蓝色为0,问题约束可以转化成要求每个2×2的方形区域的异或和为1.

如果第一行已经确定,那么后面的每一行要么是上一行的奇数列 xor 1,要么是上一行的偶数列 xor 1.那么方案数为 \(\large{2^{空行数}}\).

现在需要确认是否存在这样的合法的第一行,也就是确认每两个格子间的颜色异或关系是否矛盾.

对于每个同在第i行的已染色的格子\(x,y\),如果它们列数同奇偶,则它们在第一行的关系为\(c_x\;xor\;c_y\); 如果它们列数不同奇偶,则它到第一行一共做了(i-1)变换,它们在第一行的关系为\(c_x\;xor\;c_y\;xor\;(i-1)\).
然后用并查集维护列数,合并同行的已染色的格子,记录其与父亲的异或关系(方便O(1)求出同连通块的格子间的异或关系,判合法性).第一行的方案数即为 \(\large{2^{第一行未染色的连通块数}}\).

#define N 1000005
#define M 1000000000
typedef long long ll;
struct grid{
	int x,y,c;
	bool friend operator (grid a,grid b){
		if(a.x!=b.x) return a.xb.x;
		return a.yb.y;
	}
}a[N];
int c[N]/*col[1][i]^col[1][f[i]]*/,f[N],n,m,k,tot;
bool b[N],v[N];
inline int gf(int k){
	if(f[k]==k) return k;
	int fa=gf(f[k]);
	c[k]^=c[f[k]];
	return f[k]=fa;
}
inline bool chk(int x,int y,int t){
	int p=gf(x),q=gf(y);
	if(p^q){
		if(b[p]||b[q]) b[p]=b[q]=true;
		f[p]=q;c[p]=c[x]^c[y]^t;
		return true;
	}
	else return (c[x]^c[y])==t;
}
inline int po(int x,int k){
	int ret=1;
	while(k){
		if(k1) ret=1ll*ret*x%M;
		x=1ll*x*x%M;k=1;
	}
	return ret;
}
inline void Aireen(){
	n=read();m=read();k=read();
	for(int i=1;i=k;++i){
		a[i]=(grid){read(),read(),read()};
		if(a[i].x==1) b[a[i].y]=true;
		v[a[i].x]=true;
	}
	sort(a+1,a+1+k);
	for(int i=1;i=m;++i) f[i]=i;
	for(int i=2,x,y,t;i=k;++i){
		while(a[i].x==a[i-1].x){
			x=a[i].y;y=a[i-1].y;
			t=a[i].c^a[i-1].c;
			if((x1)^(y1)) t^=((a[i].x-1)1);
			if(!chk(x,y,t)){
				puts("0");return;
			}
			++i;
		}
	}
	for(int i=1;i=m;++i)
		if(gf(i)==i!b[i]) ++tot;
	for(int i=2;i=n;++i)
		if(!v[i]) ++tot;
	printf("%d\n",po(2,tot));
}

2017-05-03 17:56:48


本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

[bzoj2303][Apio2011]方格染色 相关文章

  1. P2486 [SDOI2011]染色

    题意描述: 洛谷 给你一颗 \(n\) 个节点的树,有 \(m\) 次操作,每次操作分为两种: 将 \(x-y\) 路径上的点赋成颜色 \(c\) 询问 \(x-y\) 的路径上的点颜色段的数量 数据范围: \(n,m\leq 10^5\) solution 树剖的经典题。 看到这个题的第一眼...

  2. 【SDOI2011 第1轮 DAY1】染色

    【SDOI2011 第1轮 DAY1】染色 题目 问题描述 给定一棵有个节点的无根树和m个操作,操作有2类: 1、将节点a到节点b路径上所有点都染成颜色c; 2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221...

  3. bzoj2442codevs4654[Usaco2011 Open]修剪草坪

    bzoj2442codevs4654[Usaco2011 Open]修剪草坪 [var1] Time Limit:10 SecMemory Limit:128 MB Submit:963Solved:478 [Submit][Status][Discuss] [var1] 在一年前赢得了小镇的最佳草坪比赛后,FJ变得很懒,再也没有修剪过草坪。现在, 新一轮的最佳草坪比赛又开

  4. 【BZOJ2395】[Balkan 2011] Timeismoney(最小乘积生成树)

    点此看题面 有一张\(n\)个点\(m\)条边的无向图,每条边有两种权值\(u_i,v_i\)。 求这张图的一个生成树,最小化\(\sum u\times\sum v\)。 \(n\le200,m\le10^4\) 构造坐标系 听说这是一种套路,然而我从未接触过。。。 考虑我们把\(\sum u\)和\(\su...

  5. PL2303在win10无法使用的解决办法

    PL2303在win10无法使用的解决办法 转载自https://blog.csdn.net/ouening/article/details/70947759 在网上购买的 PL2303 USB TO TTL 下载器安装了驱动之后无法正常使用,打开电脑的设备管理器如下图显示:图标显示有感叹号 SOLUTION: STEP1: 下载 http://pa...

  6. USB转串口TTL线在win10上不能使用芯片为PL2303

    USB转串口TTL线在win10上不能使用,芯片为PL2303 打开设备管理器,在端口中找到对应的USB转串口设备Prolific USB-to-Serial Comm Port,右键打开更新驱动程序,选择浏览我的计算机以查找驱动程序软件,选择让我从计算机上的可用驱动程...

  7. P3628 [APIO2010]特别行动队

    P3628 [APIO2010]特别行动队 题目描述 你有一支由 n 名预备役士兵组成的部队,士兵从 1 到 n 编号,要将他们拆分 成若干特别行动队调入战

  8. 「APIO2019」桥梁 题解

    先讲下部分分怎么搞。 有个非常暴力的暴力做法: 对于每一个询问,把边权大于 (w_j) 的边加入,并查集维护联通块即可。 时间复杂度 (mathcal{O(qm)}) ,可以过 (mathrm{Subtask 1}) 当 (t_i=2) 的时候,可以直接 kruskal 重构树,可以过 (mat...

  9. [APIO2010]巡逻 题解

    你谷题目传送门 题目描述 在一个地区中有 n 个村庄,编号为 1, 2, ..., n。有 n 1 条道路连接着这些村 庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单...

  10. P3643 [APIO2016]划艇

    P3643 [APIO2016]划艇 题意 一个合法序列可表示为一个长度为 \(n\) 的序列,其中第 \(i\) 个数可以为 0 或 \([l_i,r_i]\) 中一个整数,且满足所有不为零的数组成的子序列严格上升。求合法序列方案数。 思路 朴素动态规划做法为,设 \(f_...

  11. 我给猫咪染色

    “嘿嘿

  12. 我给猫咪染色

    “嘿嘿

  13. 「APIO2018」铁人两项

    知识点:圆方树 原题面:Loj、Luogu。 简述 给定一 \(n\) 个节点 \(m\) 条边的无向图,求存在多少对有序三元组 \((s,c,f)\),满足 \(s,c,f\) 互不相同且存在一条从 \(s\) 到 \(f\) 的简单路径使得 \(c\) 在路径上出现。 \(1\le n\le 10^5\),\(1\le m...

  14. luoguP3625 APIO2009 采油区域

    luoguP3625 APIO2009 采油区域 题面 题面 题解 套路题。 我第一想法是设 f [ i ] [ j ] [ k ] f[i][j][k] f [ i ] [ j ] [ k ] 为 ( 1 , 1 ) ? ( i , j ) (1,1)-(i,j) ( 1 , 1 ) ? ( i , j ) 的矩阵里,选了k个子矩阵,且最后一个矩阵的右下角为 ( i , j ) (

  15. LG P5445 [APIO2019]路灯

    Description 一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 $n+1$ 个停车站点,它们将街道划分成了 $n$ 条路段。每一路段都拥有一个路灯。当第 $i$ 个路灯亮起,它将照亮连接第 $i$ 与第 $i+1$ 个站点的路段。否则这...

  16. 染色狗

    我是一只狗,一只被染了色的狗。 我小时被商贩染了色。棕的一条,黑的一条。很像是变了色的斑马。这样做无非为的是把我买个好价钱。 没过几天,我的确被一户人家买了去。“这只狗真特别

  17. 染色狗

    我是一只狗,一只被染了色的狗。 我小时被商贩染了色。棕的一条,黑的一条。很像是变了色的斑马。这样做无非为的是把我买个好价钱。 没过几天,我的确被一户人家买了去。“这只狗真特别

  18. Luogu P5445 [APIO2019] 路灯

    很清新的DS题,话说我好久没写过DS了…… 首先我们考虑把一对路灯 (x,y) 间的答案看做点对 ((x,y)) ,那么显然有一个性质,若 (l,r) 联通,则 (u,v(lle uvle r)) 也联通 换句话说就是 ((x,y)) 为 最长的连续的1子序列 的两个端点,那么每...

  19. CF1295F Good Contest / [APIO2016] 划艇

    先离散化,设 \(f_i\) 为考虑前 \(i\) 个元素的方案数,枚举第 \(i\) 个元素处在第 \(j\) 个区间,同时枚举一起在第 \(j\) 个区间的元素个数,用组合数计算方案数,\(DP\) 过程中处理组合数就是 \(O(n^3)\) 了。 第一题要算 \(n\) 个元素...

  20. loj #10096 luogu P3627 [APIO2009]抢掠计划

    loj #10096 luogu P3627 [APIO2009]抢掠计划 analysis 缩点后,问题转化为在图中求一个起点为S,终点为某个酒吧的链使得这个链最长,于是联想到spfa,故缩点后跑一遍spfa就可以了 code #includebits/stdc++.husing namespace std;#define loop(i,start,end) f

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词