联合省选 2026 游记

· · 生活·游记

星图铺就的，未必是归途。
但有人循着它，便不算迷路。

本文不会提到任何其他人的分数。

前情提要

Day -?

参加 dmy 集训，并使用 O(n^3) 的 KM 通过了 1600 的数据。

何大哥声称网络流要崛起了。

拼尽全力学习三色花园失败。

Day 0

出发。火车上听到了机房巨佬用 AI 制作的《喷火的奶龙》，歌词里面提到了大量的 lyr。感觉旋律十分优秀，然而自己尝试之后生成了一堆史，索性放弃。

到达熟悉的酒店，然后没看通知差点忘记吃饭（？

Day 1

因为已经是第三年省选了，前两年都只是打了个酱油，再加上今年 NOIp 略高出 D 线，于是今年总想着冲出点成绩，所以还是有点压力的。

到达考场，连续第三年出现在 501。发现周围坐了 inf 个熟人，有的是现队友有的是以前的队友。

配置 FrC，建文件夹。然后很快就发密码了，具体忘了，似乎有个什么 "AK"，不敢奢求。然后看题的时候发现鼠标滚轮不灵敏，侥幸获得最后一个好的鼠标。

先通览题目，然后开始想 T1。一眼树形 dp，但是刚开始以为要同时记录概率和期望，想了 15min 无果，然后才发现只要知道每条边成为重边的概率就行，瞬间糊出 O(Tn^3) 的合并做法，加上性质 B 可以有 48 分，于是开始写。

写了 45min 才写完，感觉中间脑子有点糊。结果写完发现大样例一直过不去，又调了 45min 才发现数组没有清空，气得我当场吃了两个巧克力。

继续思考若干分钟无果，决定先把暴力打满。T2 暴力有 15 分，于是先打了。然后观察全 0 的性质，发现答案形如一个被单个的 1 分割成的连续 0，其中字典序小于 s 一定完全处于这些 0 的段里。然后答案长度不会很大，直接设 f_{i,0/1} 表示当前已经有 i 个串字典序小于 s，当前是否包含子串 s，转移即可，这样就有 30 分了。

然后思考 T3，决定先打前 12 分。打完后试图寻找性质，然而完全没有进展。观察性质却看不懂有何意义，气得我当场吃了一个沙琪玛。

只剩 1h 了啊。算了，还是回去看 T1 吧。然而此时我一直认为书上背包是 O(n^3) 的，认为完全无法优化，结果以为自己思路歪了，开始思考其它的方向，最后自然没有任何进展。

最后只有 48+30+12=90，感觉 NOIp 的优势全输完了。怎么周围人均 142？吓哭了。

尝试分析 D 队线，为了安慰自己假装 T1 非常困难，认为线应该在 110\sim120 上下。

Day 2

放手一搏吧，说不定还有机会？

开场依旧每题都看一遍。结果一点进 pdf，开头的“交互”俩字直接就把我整懵了。省选什么时候候出交互了？后来发现 T2 也是交互格式，虽然只是传统题。看来说 CCF 在向 IOI 靠拢是真的。

T1 涉及到 mex，我多年打 CF 的经验告诉我这种题一般非常可做。套路性地找到 0 的位置，然后维护左右指针，枚举要填的数 i，判断一下是在左边、右边还是在中间，在中间的话随便填，左右的话就不断移动指针找到正确位置，可以做到 2n+O(\log n) 次操作。然后没去尝试冲正解，只是拼了一堆性质，最后获得期望 72.5 分的好成绩。

尝试分析 T2 和 T3。然而 T2 暴力完全不会打，T3 始终没看懂 \{\varnothing,\varnothing,\varnothing,\{\varnothing\},\{\varnothing,\varnothing,\{\varnothing\}\}\}>\{\varnothing,\varnothing,\{\varnothing\}\} 是什么东西，只能滚回去写 T1。才发现每次询问形如一段前缀或者一段后缀，而且前后缀必定包含 0 的位置。至于找 0 的位置，可以从后往前扫，这样可以做到 n+2 次操作。再掐头去尾，把区间 [1,n] 省掉就能做到 n 次了，喜获 100 分，压力大减。

T2 依旧没想法，但 T3 似乎看懂了，似乎存在什么子树深度更大的字典序一定更大，于是对于 r=1 的情况就必须要 x=y，方案数等于路径长度，直接倍增获得高贵的 4 分。然后去想 n\le2000 的点。尝试枚举根，按子树深度从小到大计算，计算当前点时直接把子树内所有点的 rank 当成权值。写了 0.5h，调了 1h 终于通过相应的大样例，然而即使是在随机数据下也跑了 5.5s，尽管知道 CCF 少爷机，但还是感觉很不保险，于是继续寻找性质。发现不用记录整棵子树，只记录子节点也是等价的，于是做到严格 O(Tn^2\log n)，大样例跑得飞快。

快结束了，结果收到了延迟 15min 的消息，于是匆匆把 T3 菊花图的小分讨打了，又喜获 4 分。

最后估分是 100+0+24=124，感觉有戏。

Day 6

出分了，与估分分毫不差，标准分 46.5，但其他人似乎基本都有挂分。

目前来看应该是省内 rk38，没问题的话应该是可以走一趟 NOI 了。

（话说难道赛前被恶搞真的会 rp++ 吗，lyr NOIp 还落后两点几个标准分结果省选直接翻进省队了，/bx）