BZOJ 3872 [Poi2014]Ant colony

发布于 2017-04-11  245 次阅读


题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=3872

题意:在一棵有 n 个节点的树上,有一条有食蚁兽的边,当走过这条边的蚂蚁数恰好为 k 时,这些蚂蚁被吃掉。蚂蚁有 g 群,每群分别从每个叶子节点走进来,遇到 k 叉节点时分为 k-1 份离开,多余的蚂蚁就自己死掉啦 qwq.

显然对每一群蚂蚁的暴力是不能接受的,我们考虑什么情况下一群蚂蚁可以被吃掉。从关键边反过来推,由于“被吃掉”在关键边的限制很强,一定为 k,所以我们可以在经过关键边之前蚂蚁可以被吃掉的上下界,我们从两个方向遍历,更新到叶子节点。

很显然,下界即为恰好整除

上界就是 k+1 恰好整除的情况下再减 1

这样,对于每一个叶子节点,我们都有一个 mx 和 mn,只要进去的蚂蚁数量在 [mn,mx] 区间内,就可以被吃掉一次,所以我们排序后二分即可。

但是需要注意的是,经过每条边时我们需要判断一下,若这条边的下界已经超过最大的蚂蚁群数,就不需要继续算下去了,否则会出现爆 long long 的鬼畜错误。

代码如下:

 


一个非常弱的准退役OIER