2021.2 月赛题解

master_rat1 edited 4 年，2 月前

本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。

感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划，使得 EOJ 月赛能够圆满完成。此外，感谢 EOJ 运维团队为月赛提供了重要的技术支持。

最后提前祝各位同学们春节快乐！

A 昔我往矣

只要不是平方级别的算法都能过，比如虚树，树链剖分。

说一个好写的做法。先找出 dfs 序最小和最大者的 lca（也就是 $5$ 个点的 lca），算一下这两点之间的路径长度。然后把其余 $3$ 个点并到这条路径上：在加入一个点 $u$ 时，算一下 $u$ 与前面出现过的点之间 lca 最深是谁，就找到了相较于之前多出来的祖孙链部分，加到答案上去。所以只要求lca就行了。

B 杨柳依依

以每个点为起点做一遍 bfs，记录两两点对之间的最短路径长度和数量，可以通过。

也可以将起点范围缩小至出现过的 $2 k$ 个点，常数会小一些。

C 今我来思

给出的条件等价于： $\forall i \in [l, r] ， p_{i} \geq x$ 且至少一个 $i$ 取到等号。对于每个 $i$ 来说，计算包含 $i$ 的所有 $[l, r]$ 对应 $x$ 的最大值，也就是用线段树得到 $p_{i}$ 的理论下界。如果把这个数列带回询问都有无法满足的，那么显然最终无解。接下来要考虑如何满足“排列”这一限制。

我们从小到大考虑所有的 $i$ ：它应该被填在排列的哪个位置？首先，一定是在所有满足 $x = i$ 的 $[l, r]$ 交集中（交集为空，则无解）若无 $x = i$ 的询问，则相当于没有限制。其次，一定是某个下界 $\leq i$ 的位置（当然是之前没占用掉的），然后直接钦定这两部分交集中任何位置填上 $i$ 即可。

这样填出来的排列一定是符合条件的，具体实现需要一个或两个 set 辅助。（这题方法应该挺多的。）

D 雨雪霏霏

所有格子的海拔自始至终都不变，所以我们一开始建一个 Kruskal 重构树出来。在本题中，可以将所有格子按照海拔从小到大考虑，对于当前格子 $u$ 和周围的某个海拔低于 $u$ 的格子 $v$ ，将 $u$ 设为 $v$ 所在树的根的父亲。比如样例 $3$ 建出来的树长这样：

在这棵树中，点 $u$ 是点 $v$ 的祖先 $⟺$ 从 $u$ 出发走四联通、海拔不超过 $L_{u}$ 可以到 $v$ 。拓展一下，从 $u$ 出发走四联通、海拔不超过 $L$ 可以走到的点，是 $u$ 的祖先中海拔 $\leq L$ 且深度最浅的那个点的子树。找这个点可以用倍增，所以通过 dfs 序，原问题就转化到序列上了（即子任务 $4$ ）。

序列上计算一段区间内不同颜色数有一个方法：定义 $n x t [i]$ 表示最小的 $j > i$ 满足 $c_{j} = c_{i}$ ，若不存在则设为 $inf$ 。那么区间 $[l, r]$ 内不同颜色数就是 $i \in [l, r]$ 且 $n x t [i] > r$ 的个数，可以用树套树解决。用树状数组+动态开点线段树的空间+时间比较稳一点。

跳 $n x t$ 相当于对每种颜色建立的一条链，修改就是在链上做插入和删除，进而修改 $n x t$ 。所以只要对每种颜色开一个 set 即可。

建出Kruskal重构树后的另一种做法是带修莫队，这里就不展开了，也可以通过本题，实际耗时更小。

8 1

_Kubic_

4 年，2 月前

出题人叫我喷，所以我就来喷了。
喷喷喷喷喷喷喷喷喷喷

回复 8 0

Gricew

4 年，2 月前

建议回到两月一场，整点好题

回复 5 0

interestingLSY

4 年，2 月前

C 题一个线段树即可：Me

回复 2 0

寒鸽儿

4 年，2 月前

被锤爆了，5555

回复 1 0

火月之心

4 年，2 月前

请问一下，有没有java提交模板，除了符合开头正则以外，其他内容如方法名不知道如何定义。

回复 0 0

MAOoo

4 年，1 月前

这场有抱枕吗？

回复 0 0

Once

4 年，1 月前

奖项设置等开学后再安排。

回复 0 0

interestingLSY

3 年，11 月前

抱枕发了喵？

回复 1 0

Once

3 年，11 月前

五一后发。如果抱枕不足的话，会发一些别的东西。

回复 1 0

tommy0103

4 年，2 月前

这题为什么这么屑啊
T1数据范围太水
T2强行多合1
T3一眼题
T4也非常一眼

所以这么屑的题有出的必要么（恼

回复 12 8

杰斯守护未来

4 年，1 月前

救世啊

回复 0 0

jj6666

4 年，2 月前

麻烦问一下怎么能看到题目的测试数据

回复 0 0

Once

4 年，2 月前

在题目集中提交可以看到数据。

回复 0 0

A 昔我往矣

B 杨柳依依

C 今我来思

D 雨雪霏霏

Comments

服务

开源

关于我们