[APIO2011]方格染色
2021-07-16 00:14
标签：for sample 格式 sam 红色 就是 str ora algorithm Sam和他的妹妹Sara有一个包含n*m个方格的表格。他们想要将其中的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2*2的方形区域都包含奇数个（1个或3个）红色方格。例如，下面是一个合法的表格染色方案（R代表红色，B代表蓝色，原来是张图）： B B R B R R B B B B R R B R B 可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格依然满足他们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？ 输入格式： 输入的第一行包含三个整数n，m和k，分别代表表格的行数，列数和已被染色的方格数目。 之后的k行描述已被染色的方格。其中第i行包含三个整数x[i]，y[i]和c[i]，分表代表第i个已被染色的方格的行编号、列编号和颜色。c[i]为1表示方格被染成红色，c[i]为0表示方格被染成蓝色。
输出格式： 输出一个整数，表示可能的染色方案数W模10^9得到的值。（也就是说，如果W大于等于10^9，则输出W被10^9除所得到的余数）。 对于20%的测试数据，n，m
对于50%的测试数据，n，m
对于100%的测试数据，2
首先发现，如果我们把蓝色看作1，把红色看作0，那么对于每一个格子a(i,j)，都有：a(i,j)^a(i+1,j)^a(i,j+1)^a(i+1,j+1)=1 那么只要第一列和第一行确定了如何染色，整个表格的染色就确定了 如果(x,y)的值为1/0那么第一行和第一列的值就会有限制 如果(x,y)都是偶数，那么2*2的矩形总数为奇数，异或和为1 而且除了(1,1),(x,1),(1,y),(x,y)以外其它格子都异或了2次 所以a(1,1)^a(x,1)^a(1,y)^a(x,y)=1 即a(1,1)^a(x,1)^a(1,y)=a(x,y)^1 否则就是a(1,1)^a(x,1)^a(1,y)=a(x,y) 所以讨论a(1,1)的值可以得到a(x,1)和a(1,y)的值的异或关系 也就是说，存在下列关系 相同，不同，关系不确定，前两种都是连通，只不过关系不同 所以用带权并查集维护 d[x]表示x与他的根是相同还是不同 特别注意当确定了第一行/列的值时 那么该联通块的值就确定了 pd[x]表示x的值，不确定为-1 如果中间冲突返回0 最后结果是2^不确定值的联通块数 a(1,1)=1的情况吧所有a(x,y)^1就行了 [APIO2011]方格染色 标签：for sample 格式 sam 红色 就是 str ora algorithm 原文地址：https://www.cnblogs.com/Y-E-T-I/p/8909095.html题目描述
输入输出格式
输入输出样例
3 4 3
2 2 1
1 2 0
2 3 1
8
说明
1 #include
下一篇：[APIO2013]机器人