联合省选 2025 游记

· · 生活·游记

Day -1

下午去佛山市南海中学报道。

回来的时候打了一辆车牌号含 DS 的车（笑。

回来 3 点多发现自己前几天熬夜熬脱了，非常头痛。于是在床上躺着试图睡觉，于是 1h 过去了，尝试失败，于是下楼打乒乓球。回来终于有了困意，成功睡着。结果晚上 12:00 鼻炎发力了，直接给我弄醒，费了好大劲才睡着。

Day 1

早上起来头疼欲裂，幸亏我是体验。

浑浑噩噩到了考场，考试终于开始了。

直接看 T1，什么中位数数数题，感觉好神秘，第一眼没什么思路，于是去把 T2，T3 也看了，T2 大 DS，T3 给的性质好神秘。

于是开 T1，突然反应到可以作为中位数的数一定是一个连续区间除去不可能出现的数，于是分别二分这个区间的左右端点，直接贪心 check 即可，然后就是离散化，找出这个区间内所有可能出现的数。然后 1h 过掉了所有大样例。

小插曲：在使用 NOI Linux 测 T1 代码的时候忘记运行指令是什么了（悲。

继续开 T2，是最喜欢的 DS，发现 20pts 是简单的。然后不知道为什么突然想到了“整体二分”四个字（NOIP 后遗症罢！），然后发现自己不太会带修整体二分，于是弃掉，开 T3。

突然发现 T3 的数据性质就是假设将 a_{i},b_{i}，看作一个 [a_{i},b_{i}] 区间，那么这些区间要么包含，要么不交。然后就不会了，感觉 8pts 的暴力 O(Tn!n^2) 好像跑不过，重新去看 T2。

会去写完了 T2 20pts 暴力。

看 T2 特殊性质，感觉性质 B 好像是线段树，直接敲完一个线段树之后发现自己假掉了（漏看了查询 3 还要输入一个 x），然后发现好像可以线段树合并加可持久化线段树，然后发现只有在树上才能怎么做，DAG 上不行，于是直接原地爆炸。

于是又回去写 T3 暴力，写完后发现跑得飞快，开心。

考试结束。

预估：100+20+8=128。

出来发现大家都是这个分，不过上了一百，我还是很高兴的。

晚上默写了 T1 代码，交上云斗过了，开心。

晚上闲着没事看印度电影。

顺便写了最不熟悉的网络流模板。

Day 2

Day 1 下午休息好了，Day 2 早上精神多了。

开考直接开 T1，发现好像是一个很普遍的技巧：直接将箱子按 t_{i} 从小到大排序，然后直接一个一个推到位即可，于是 1h 写了个 O(n^{2}) 暴力并通过了小数据大样例，证明结论正确。处理箱子移动实际上就是 ABC 某场比赛的 F 题，又花了一会写完了 O(n \log^{2} n) 的解法，发现大样例普遍 0.5s，还挺快，但是看在这次机子慢，还是写了线段树二分 O(n \log n) 的解法。接着尝试对拍，但是造出的数据不是全 Yes 就是全 No，不管了，反正我是体验。

此时已经过了 2.5 h，接着去看 T2。感觉 A 性质大爆搜有点难写。发现 B 性质非常优美——就是整张图只有一棵最小生成树，于是开始想 B 性质，不久就会了。

设 f(S) 为对于集合 S 中的每一个点，都能作为生成的图 G' 中外向最小生成树的根的概率。那么可以搜索，将 S 中一个点钦定为根，按照 DFS 序依次考虑集合 S 中的每个点（即每次遍历到一个 S 中的点，考虑在原来基础上要加多少条有向边才能满足这个点为最小外向生成树的根）。最终使用容斥——减掉所有包含集合 S 的集合 T 的 f(T)。最终答案就是 \sum f(S)，时间复杂度 O(T(n \times 2^{n}+3^{n}))。

于是写写写，光速过掉了唯二的 B 性质样例。然后再会去想 A 性质的爆搜，发现好像直接二进制枚举有向图边集，对于这个边集的所有子集，判断一下是否是最小外向生成树即可，时间复杂度是 O(T(3^{2m} \times n \times (n+m)))。

A 性质也写得挺顺利，过了唯四的 A 性质样例——貌似挺快的。

最后就是把 T3 的 8pts 状压爆搜写了。

考试结束。

预估：100+24+8=132。

赛后听 lxr 说 T3 状压改成直接数组爆搜加双模哈希就能拿 32pts，好神秘。

总之是考完了！好像对于我这个菜鸡还不错。

总共估计：100+20+8+100+24+8=260。

希望 D2T1 不要挂分。