高度由习惯堆积

分类 OJ:POJ 下的文章

February 17, 2019

POJ1417 True Liars(并查集)

题目有一群好人和一群坏人,好人永远说真话,坏人永远说假话。现给出一组话,问能否唯一确定每个人是好人还是坏人。样例输入: 2 1 1 1 2 no 2 1 no 3 2 1 1 1 yes 2 2 yes 3 3 yes 2 2 1 1 2 yes 2 3 no 5 4 3 1 2 yes 1 3 no 4 5 yes 5 6 yes 6 7 no 0 0 0
February 17, 2019

POJ1182 食物链(经典带权并查集 扩展域)

题目动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是"1 X Y",表示X和Y是同类。 第二种说法是"2 X Y",表示X吃Y。 此人对N个动物,用上述两种说法,一句接一句地说出K句话...
February 15, 2019

POJ1741 Tree(点分治)

题目给一棵边带权树,问两点之间<=K的点对有多少个。思路题目很简单,但是思路很经典。首先确定点分治的基本框架,假设一定要经过一个根。下面还要用到容斥的思维。对于一个根,我们没法直接统计路径长度不超过k的路径条数,那需要一点技巧。处理出子树中所有的dis值放入B数组中,再对于当前A子树,加上其对于B所做的贡献,减去其对自身所做的贡献,就是它对其他子树所做的贡献。看似简单,其实在点分治问题...