Monthly Archives: February 2010

这个应该也算是并查集的一个扩展，需要加字段来判定子节点是否和父节点属于同一个帮派。 和食物链那道题很类似。

参考吴文虎的讲义，对每个节点，定义一个数组 rank， if rank[i] = 0，说明节点 i 与父节点同类； if rank[i] = 1，说明父节点吃子节点 i； if rank[i] = 2，说明节点 i 吃父节点。

M 1 6 将 1 移动到 6 的上面； M 2 4 将 2 移动到 4 的上面； M 2 6 将 2 和 4 移动到 1 和 6 的上面。

合并，找出那些合并后根节点为 0 的即可。

将一定数量的钞票变换，放到 b 数组当中，然后背包，这是滚动数组的应用。 参考： http://www.cnblogs.com/asuran/archive/2009/10/13/1582167.html http://blog.sina.com.cn/s/blog_5c95cb070100cyjw.html http://hi.baidu.com/gada_sun/blog/item/44097ec017c53b3fe4dd3b6a.html 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 … Continue reading →

这个题目使用并查集貌似很直接。相同宗教信仰的属于一个并查集。

修复电脑网络 亚洲海底地震，使得所有的电脑都坏了并中断了联系，现在有一群维修人员被派往现场修复。 他们在那边会做两件事， 1、“O” 代表要修复某编号的电脑，“S” 代表要测试两台编号不同的电脑是否可以连通，测试成功，则输出成功，否则失败。但是两台电脑之间如果要直接连通的话，它们之间的距离不能够超过 OJ 提供的距离 D，如果超过的话，他们要连通的话，中间就要有中介电脑才行。现在你的工作就是根据修复人员所做的操作，输出成功或者失败。 解题思路：这道的话就是属于互通的题目啦，也就是要用到并查集。修复一台电脑就标记为修复过了，然后跟其他已经修复过的电脑进行合并，但是合并的条件必须是两台电脑的距离小于 D。当要测试两台电脑时，就是判断他们的根结点是否一样或者是距离小于 D，然后再进行合并。 http://blog.csdn.net/q3498233/archive/2009/08/14/4447965.aspx

这个本质上是图的着色问题，要求相邻的节点使用不同的颜色，问至少需要多少种颜色。 深度遍历，看看已经使用了哪些颜色，能否对将要染色的节点染一个和邻接点不同的颜色，如果不能找到，则得染一个新的颜色了。

博弈，两人轮流切割矩形，直到一方无法继续切割为止。

题目大意：一个教授研究虫子的交配，你认为这种虫子只和异性交配，现在要验证他的观点，他把虫子编上号。 通过大量的数据，现在你要来判断他的想法是否正确。 解题思路：把有交配记录的虫子做成一个并查集，通过它到根的长度的奇偶性判断虫子的性别； 参考： http://blog.csdn.net/logic_nut/archive/2009/07/19/4362322.aspx http://blog.csdn.net/super_chris/archive/2009/09/18/4568241.aspx