Visits: 393

有点难。

简单模拟就好了。

一开始以为是聚类。

后来知道是并查集。

甚至不需要路径压缩等技巧，裸的并查集，直接开长度为 N 的数组，每次要合并的时候遍历，修改需要合并的所有值为 p 的改为 y 就行了。

输出格式感觉是专门为 Python 定制的啊，很鄙视。

输入：

并查集：

Point 是一个类。

输出：

这道题我觉得有点难。

一开始以为是贪心或者什么，后来想想是不是线段树，但是显然线段树求区间最值、区间和，没法维护每一段的状态。

考试结束以后问 zerol，他说不可能是线段树这么难的，肯定是简单算法。

一开始他给出的是差分维护，就是遇到左端点 +1，遇到右端点 -1，找最大区间。

后来看到样例 2，就感叹我抽题的运气不好。

第 2 个样例的输出是

 1 2
 2 3
 3 4
 4 5

也就是弹幕最多的时间是 4 段，每段都是 1，不能合并的。

而且题目是开区间，很诡异。

林的建议是，加一个 .5 区间，搞成左开右闭或者左闭右开，这样就把开区间的问题解决了，可以差分了。

但是第 2 个样例输出 1 5 还是分 4 段，还需要考虑。

最后一题是 DP。

大概的提示和扔鸡蛋测试最高每个鸡蛋能扔多高是一样的。

题目是说给你 K 架飞机，测试最大拉伸高度。

样例 1 是 1 架飞机，1000 米，那就必须测试 1000 次了，因为飞机损坏了就没有了。

样例 2 是 15 架飞机，1000 米，由于飞机足够，用二分。

其实这两个特殊状态出去已经有一些部分分了。

关键的部分是 DP。

就是 ​$f(h, k) = min_{0 < i \leqslant h } { max{f(i,k-1), f(n-i-1,k)}} + 1​$