【随笔】省选联考 2025 游记

Day -1

整天呆在机房，上午打了 nfls 最后一场省选模拟赛，三道题全都挂分了，下午补了题顺便看了眼 HBOI 出的模拟赛，T1 想到了一个 $\mathcal{O}(n \sqrt n \log n)$ 的乱搞做法但是 TLE 成了 $90$ 分，加了一个根号分治的记忆化极限卡过了。

Day 0

上午 $11$ 点整起来的，但还是很困，吃完饭就赶去火车站了，中途还把身份证落在出租车上了……到达上饶已经快六点了，吃完回到家就顺便看了一下自己的笔记，顺便刷了刷 LA 群，虽然这次比赛已经无所谓了但还是很紧张，大晚上的睡不着觉，差不多凌晨两点才完全入睡。

Day 1

睡了 $5.5$ 个小时，起来有些神志不清了，去餐厅随便吃了点早饭（感觉完全没有怎么吃），徒步前往考场。到考场已经 $8:10$ 左右了，随手发了条朋友圈，然后排队进入考场，当时到了一堆人啊。查完身份后坐到机位上，是非常舒服的~~看片位~~角落，而且我右边的人缺考了，非常好。

打开编辑器的那一瞬间就感觉不对劲，没错，这键盘延迟高的离谱，感觉不会打字了，把显示器刷新率调回 60Hz 后状况没有变好，不管这么多了，剩下十几分钟赶紧把缺省源打完。打到快输的时候开考了，通读了一下所有题目，T1 很好懂，感觉也可做。T2 逆天的时间限制和空间限制还有数据范围不禁让人浮想联翩，多刷 Ynoi 的第六感告诉我要么是 ds 要么 bitset 优化，果然后者被我猜对了（但没什么用），T3 感觉很不可做。

回到 T1，观察了一下性质 A 和 B，感觉性质 B 很直接，先考虑一下 A，再套一个离散化应该就行了。首先枚举中位数，然后判断是否合法。我冥冥之中口胡了几个结论，例如中位数个数尽可能多一定不劣，同时中位数前后的个数上下界可以分别确定了。

想到这里差不多了，但是当时有点神志不清了，暂时没有什么优美的做法，先写了 $\mathcal{O}(n ^ 3)$ 的暴力，然后挂了，然后 debug 发现这暴力假了但是也可以优化。不管了，先保证正确性，花了 $30$ min 乱搞出了一个绝妙的做法，把预处理和 check 的复杂度降为了 $\mathcal{O}(n ^ 2)$ 。

然后把一堆注释和 debug 删了，发现预处理就是一个前缀和和一个后缀和还有一个差分，直接线性（不知道当时怎么先写的 $\mathcal{O}(n ^ 2)$ ）关键在于 check 还是 $\mathcal{O}(n ^ 2)$ 的。

不管了，先套一个离散化，感觉知道是离散化的话很自然，因为性质很显然，这里没有什么阻碍。

然后发现 check 中在性质 B 的时候可以做到 $\mathcal{O}(1)$ 的，以防万一我也写上了。

现在关键就是一个问题，知道一个中位数的个数和它前面后面所有数分别的总数上下界，判断是否合法。现在想想我真是唐完了，我先写了一个判断无解的，发现答案仍然偏大，然后我乱搞了一个枚举的做法，时间复杂度 $\mathcal{O}(n ^ 2)$ ，已经能拿 $90pts$ 了。然后我就跳了。

此时已经过半了，看 T2，看半天数据范围不知道是什么，然后根据之前的猜想试了一下大小为 $10^5$ 的 bitset<100000> 数组，发现内存刚好差不多 $1$ GB，看起来确实可以维护 DAG 的可达性。

先写了 $20$ 分的暴力，然后看性质，性质很多感觉高低得捞一点把，先写个可达性统计先。然后我又糖了，题目暗示本身就是一个 DAG，我没注意到，还写了一个 Tarjan 维护，代码变得又臭又长，不知道如何下手了。

盯着 A，B，C 性质看半天，最后选了一个 AC 性质的，要求每次询问可达路径中点数最大的，支持单点权值交换，但是想半天还是不会，最后写了一个特殊性质的暴力。

就剩一个半小时了，转过头去看 T3，T3 显然比 T2 不可做，打了一个 $\mathcal{O}(Tn!)$ 的 $8pts$ ，应该有吧。性质怎么跟树扯上关系的没有管，还以为 T2 性质更好拿，没想到 T3 有 $44pts$ 更可做。

最后一小时看 T1，想了枚举二分啥的都不行，然后我突发奇想把所有本身不合法却判定错误的数据输出出来，才发现它们本身就不存在，加上一个特判就满分了。

直到最后都在想 T2，但是没结果，可惜了。拿了一个大众分： $100 + 20 + 8 = 128 pts$ 。

回去一直再刷 LA 群，T2 的解法杂七杂八的，有人还说 T3 在 nfls 有人搬过原题，当然我太菜了看都没看，唯一懊悔的就是没有及时看 T3 的特殊性质，很多人大众分 $172 pts$ 都是做了 T3 的部分分。

Day 2

睡眠质量略好于昨天，起的也比昨天早。但是早上没有去餐厅吃早饭，然后再次赶往考场。

自然地到的比昨天早，差不多半个小时的时间，闲得无聊默写了网络流和线段树的模板，还看了会昨天写的代码。

题面下发了，直接盯着第一题看，很显然的可以想到一个时间戳从小到大的一个贪心并且模拟即可。然后顺着思维写了一个 $\mathcal{O}(n ^ 2)$ 的做法，轮到每一个人就暴力检查所有人的位置是否合法。但是这份暴力我居然大样例挂了，调了大约半小时才发现整体平移写挂了。剩下来的事情大概就是将暴力筛查的时间复杂度降到线性以下。

这绝对是数据结构，而且暴力代码验证了一个人只会往一个方向移动，否则就无解。但是严格偏序的关系使得我要维护一个公差为 $1$ 的等差数列，这不好用线段树或平衡树实现。然后我想到了珂朵莉树，我觉得 set 可以很好的维护这个连续段的关系，但是我当时没打算写（最后悔的一集），毕竟我珂朵莉树只写过 $eps$ 次。时间过去了将近两个小时，我隐约感觉这题能上紫，目前拿了 $44pts$ 而且性质还没着手写，然后开始看 T2。

T2 显然的 NP 问题，有向图的生成树概念还是第一次听说，读题读了好久才想到一个暴力的思路。刚好给了较为富裕的 $8pts$ 的 $\mathcal{O}(4 ^ m \times n ^ 2)$ 做法，我就无脑写了一个暴力，然后用 prim 算法每一个点跑一次，判断这个点是否是合法的，这样的话时间复杂度是 $\mathcal{O}(4 ^ m \times n ^ 3)$ 的，但是还是可以过的，就是写了非常的久。然后考虑特殊性质 B，性质也算比较好想，算是 MST 中的一个典型 trick，时间复杂度也刚好够，我直接在原来代码的基础上修正好了。写完后测了一些大样例，突然发现我第一部分的纯暴力写挂了，答案总是偏小，这大概率是算法的问题还是啥的，我看了半天代码没发现问题，直到出考场才直到我那一部分是 fake 的，然后这 $2$ 小时就被耗费拿了 $12pts$ 了。