联合省选2025游记

· · 生活·游记

闲话

梦里不知身是客，一晌贪欢。

我对 OI 的热爱和投入都不比别人多，我凭什么觉得自己总是能当那个幸运的被选中的人呢？近几个月对 OI 的兴趣远不如以前，训练总有一种平淡无趣打卡上班的感觉，对更进一步并没有什么信心。当时的我其实已经模糊的意识到自己继续打 OI 大概只是在用白日做梦的方式逃避文化课，但做美梦的人是不会叫醒自己的，只会等待梦境痛苦地破碎。得益于去年幸运之神的眷顾，我的 OI 生涯基本没什么遗憾，就这样结束也不一定是坏事。真正的审判还未到来，不过无论如何，现实都是必须要面对的，不能在一个梦破碎后沉溺于另一个梦中。

Day1

开 T1，想着想着忘了 a 和 b 都是区间，开写前又看了一眼题才发现，但其实没啥区别，快速在开场 30min 左右通过大样例，感觉过的应该不算慢。

开 T2，一看 6s+2048MB 和 1e5 的数据范围，感觉像根号，想到前几天见到的根号重构。发现 \sqrt q 个询问可以一块做到 \frac{m\sqrt q}{w}， 稍微又想了一会，大概 1.5h 到 2h 写对，没卡常，最后一个大样例 5s，感觉可能要卡一点常，但先扔了去做 T3。

开 T3，看起来比较困难，先考虑树的部分分，发现限制大概是一个以最小值为根，然后每个子树都在序列中是一段区间的形式。几个树拼起来就是要求不存在 x 放了一半开始放 y， y 放了一半再继续放 x 的形式，用栈和优先队列维护即可。之后在想每个树内部如何求序列时想错了，觉得递归进子树之后还可以换根，需要写一个树状数组和链表维护一个做一个类似启发式合并的过程。写了很久，样例错了和暴力拍才发现递归下去之后子树内不能换根，直接 dfs 就行，花了 15 到 30min 改完，最后十几分钟写完。

预计得分 252，当时出场感觉应该比大众分高的不多，但似乎其实高了不少，不过基本都没拍。

Day2

开 T1，一眼按时间排序贪心移动，直接上了一个值域线段树维护，写的很蠢，写了一些线段树上二分，区间赋值，区间查询。大概 1h 多一些过了大样例，感觉不是很好拍就先去看 T2 和 T3 了。

开 T2，感觉不好做，想了挺久才想到 B 性质的容斥，之后感觉 C 性质比较可做，但想了好多种容斥，dp 的方式，怎么都会重，最后有一版很麻烦，空间复杂度爆炸，还只能过 n\le 12 的，写到最后一个部分才发现我不会做数强连通子图，最后暴力+B 性质跑路看 T3了。

开 T3，看起来就不好做，看 AB 性质，想了一个分为递增前缀，递增后缀，前缀最小元素大于后缀最大元素，前缀中数 -1 次数比后缀少一次的结构。但 dp 的话需要枚举 -1 次数，然后就感觉可能会算重，但想了一会想不到别的结构，就只写了个 8 分暴力。

最后二十多分钟，没什么想法了，把交的代码都验了一遍，回去打 T1 对拍，最后十分钟才写完拍。拍出来一下就挂了，查了几分钟，发现是有一个边界写错了，但刚开始改就已经结束了。

最后预计得分 68 到 132。

后记

出场心态就崩了，很难想象还有这么绝望，搞笑的事情。

很难接受自己这么蠢的表现，对数据强度进行了一些幻想，但可能是太过不切实际，这个幻想连欺骗自己都无法实现。