钥匙的[联合省选2026]游记

· · 生活·游记

本来早就退役了的，但莫名其妙地走到了省选，那就打一下吧。

无名众神牛逼！

一些前置经历

坐标 HN，NOIP 乱搞拿了 140 分，过了 2= 线和全国 1= 线，全校第一，可见我们学校之菜，因为我是全校历史第一/今年唯一的一个省选牲。

寒假年前搞了下集训，年后打摆，一直到省选前也没怎么准备过。旁人看起来：省选以前，这个人总自夸着“绰有余裕”，是事实；不久就不再自夸了，只希望着有时间集中突破，也是事实；现在是既不夸自己，也没时间突破，改为一味求神拜佛，怀古伤今了——却也是事实。

如今也只能自作自受罢。

玄学

Day 1

从湘江新区到长沙市一中很远，6点多就出发了，做了近两个小时的地铁，昨天晚上有点小失眠，在地铁上狂睡。

8点出头就到了，进考场抽机子，太好了不是渣机，但是渣键盘，编码速度-=inf。

看T1，神秘树上背包，赛时写了个 O(n^3)，大致思路就是枚举每个结点，对其子树大小与其至父亲的边为轻边的概率，难点在求边为轻边的概率。设 dp_{u,i} 表示以 u 为重链头，长度为 i 的重链概率，f_{u,i} 表示 u 的儿子节点的重链长度和为 i 的概率，然后求出所有长度和的逆元总和，这样就可以求出树边为重链的概率，和 1 减一下就是轻边的概率了。

dp 和 f 都可以直接跑背包求出来，于是做完了。

但没过样例，寄。

T2疑似神秘构造，写特殊性质，但突然忘了字典序的定义了，带了长度，疑似伪了。

T3没写出暴力。

Day1 大败，[8,16]+[0,15]+0=[8,31]。

下午王女从学校回来了，得到了王女的祝福，Day2 加油！

Day 2

早餐是美味的方便面。

提早10分钟开题，俩交互？捣鼓了1h的命令行，失败了，回去一定恶补英语。测不了交互故开T3，半小时狂轰菊花图和 r=1 的特殊性质，开始神秘分讨，展开了 2^3 个分支，然后过样例了。后尝试了 r=2，未果，随后洪文了写了个 O(n^3\log n) 大暴力，每个节点开个 vector 记录节点 u 的所有孩子节点，按要求的权重大小降序排序，cmp 函数是神秘的 O(n) 递归比较，卡不过 2000，寄。

滚回去想 T1。很熟悉，是的，这题半年前见过，和之前无聊搓的一个废题相像，但当时因为不会写交互库把它删了，而且当初问了 DS，它说无解。哦，这题满足子区间 mex 相同就可以啊，我糖了。

思路是先扫前后缀，产生 mex 改变的新生节点的值得以确定，瞪样例发现第一个和最后一个也可以顺便确定，随后给每个值安排一个取值范围，对于区间 [l,r]，所有小于其 mex 的 k 一定在区间内，依此可以求出包含其的最小区间。然后对于每个 k 的取值区间 [l,r]，若位置 l 或 r 的取值已经确定，可缩小区间边界，这样又可以确定一些数的位置，重复操作直到无法缩小任意数的位置为止。

然后我就不知道还有什么方法确定数了，直接把剩下未确定的随机分配了，不会自己测交互，人脑测是过了样例的。然后认为交互题不需要文件操作把 freopen 删了，代码过了编译就没管那么多了，感觉大概率寄了。

然后搓T2暴力，中途T3题面有锅，滚回去瞪，没啥收获，浪费时间。然后因此时间延长了十分钟，但依旧没挣出暴力，输。

感觉 [0,32]+0+[12,20]=[12,52]

总分 [20,83]，难绷。

后话

回去路上凹大决战，鸡撕拉比格玆好打，进一梯队了，下周看能否稳二梯队。

已经被 ios 的负优化惹怒了，模拟器启动，机房摸鱼选项又多了一个，耶。

成绩：

Day1：T2 伪了，光荣吃下线，8 pts。

Day2：选手文件假了，少打了个零，光荣了。

怎么两位数都没保住？？

考好中考继续陪王女混吧嘟嘟嘟。