出题人叫我喷,所以我就来喷了。
喷喷喷喷喷喷喷喷喷喷
master_rat1 edited 3 年,6 月前
本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。
感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划,使得 EOJ 月赛能够圆满完成。此外,感谢 EOJ 运维团队为月赛提供了重要的技术支持。
最后提前祝各位同学们春节快乐!
只要不是平方级别的算法都能过,比如虚树,树链剖分。
说一个好写的做法。先找出 dfs 序最小和最大者的 lca(也就是 $5$ 个点的 lca),算一下这两点之间的路径长度。然后把其余 $3$ 个点并到这条路径上:在加入一个点 $u$ 时,算一下 $u$ 与前面出现过的点之间 lca 最深是谁,就找到了相较于之前多出来的祖孙链部分,加到答案上去。所以只要求lca就行了。
以每个点为起点做一遍 bfs,记录两两点对之间的最短路径长度和数量,可以通过。
也可以将起点范围缩小至出现过的 $2k$ 个点,常数会小一些。
给出的条件等价于:$\forall i\in[l,r],p_i\ge x$ 且至少一个 $i$ 取到等号。对于每个 $i$ 来说,计算包含 $i$ 的所有 $[l,r]$ 对应 $x$ 的最大值,也就是用线段树得到 $p_i$ 的理论下界。如果把这个数列带回询问都有无法满足的,那么显然最终无解。接下来要考虑如何满足“排列”这一限制。
我们从小到大考虑所有的 $i$:它应该被填在排列的哪个位置?首先,一定是在所有满足 $x=i$ 的 $[l,r]$ 交集中(交集为空,则无解)若无 $x=i$ 的询问,则相当于没有限制。其次,一定是某个下界 $\le i$ 的位置(当然是之前没占用掉的),然后直接钦定这两部分交集中任何位置填上 $i$ 即可。
这样填出来的排列一定是符合条件的,具体实现需要一个或两个 set 辅助。(这题方法应该挺多的。)
所有格子的海拔自始至终都不变,所以我们一开始建一个 Kruskal 重构树出来。在本题中,可以将所有格子按照海拔从小到大考虑,对于当前格子 $u$ 和周围的某个海拔低于 $u$ 的格子 $v$,将 $u$ 设为 $v$ 所在树的根的父亲。比如样例 $3$ 建出来的树长这样:
在这棵树中,点 $u$ 是点 $v$ 的祖先 $\Longleftrightarrow$ 从 $u$ 出发走四联通、海拔不超过 $L_u$ 可以到 $v$。拓展一下,从 $u$ 出发走四联通、海拔不超过 $L$ 可以走到的点,是 $u$ 的祖先中海拔 $\le L$ 且深度最浅的那个点的子树。找这个点可以用倍增,所以通过 dfs 序,原问题就转化到序列上了(即子任务 $4$)。
序列上计算一段区间内不同颜色数有一个方法:定义 $nxt[i]$ 表示最小的 $j>i$ 满足 $c_j=c_i$,若不存在则设为 $\inf$。那么区间 $[l,r]$ 内不同颜色数就是 $i\in [l,r]$ 且 $nxt[i]>r$ 的个数,可以用树套树解决。用树状数组+动态开点线段树的空间+时间比较稳一点。
跳 $nxt$ 相当于对每种颜色建立的一条链,修改就是在链上做插入和删除,进而修改 $nxt$。所以只要对每种颜色开一个 set 即可。
建出Kruskal重构树后的另一种做法是带修莫队,这里就不展开了,也可以通过本题,实际耗时更小。
奖项设置等开学后再安排。
抱枕发了喵?
五一后发。如果抱枕不足的话,会发一些别的东西。