GDOI2025 游记

缪凌锴_Mathew · 2025-03-11 16:35:58 · 生活·游记

省流：乱搞 D1T2，反向挂分。

Day 0

试机，发现不仅有 VSCode + cph、CPEditor 的豪华配置（我无所谓，有 Sublime 就行），本地机子还特别快。

据说评测机特快。

Day 1

10 分钟配完了 Sublime，看了眼 T1。

区间并集的每一段互相独立，其中中间一段贡献是 1，感觉是直接算出下界然后二分。（事实上许多人都是这个做法）

但是我懒，懒得离散化和算出具体下界。

发现可以直接边扫边做，每个点算出包含它的、左侧的、右侧的区间个数 l,r 和就行了。

本质不同的点个数是 O(n) 的，时间复杂度 O(n\log n)，瓶颈在排序，不用任何 DS。

由于我比较唐调完后 9\!:\!30 了。

之后看 T2，时限 6s、空限 2G？？？这不对吧……

第一想法是按某种方法编个 dfn，然后每个点可达的 dfn 区间都较少，然后 DS 维护 a,b。

然后码出来发现大样例这个区间数量有几千，寄了。

想了一个小时左右，放弃了，先看 T3。

半个小时后发现树（AC 性质）似乎比较好做，直接贪就完了。

具体地，每次跳到子树最小值，子树满了则跳父亲，DS 维护一下就行了。

发现 C 性质（森林）就是要在这个基础上给每棵树的根定个顺序，也是贪心，set 维护即可。

还是由于我比较唐调了特别久， 12\!:\!40 了。

获得 52 分，满意。回去打 T2 暴力。

既然我 T2 都写了一份 dfn 区间的获取，那我不妨顺手用一下，遍历这些区间就完了。