2026 联合省选游记

· · 生活·游记

Day -1

当我以为我下次遇到这些题目的时候就是 ACM 时：

获得重要剧情道具：联合省选准考证 x1！

那我还说啥了，上呗

Day 1

不知道为什么吃拉肚子了，紧急前往考点学校上厕所。

八点半发完压缩包密码，浏览了一遍题目，发现 T1 貌似简单，T2 看起来像神秘串串题，T3 看起来像神秘构造题，总之一点都看不懂，先看 T1。

本来以为 T1 直接简单期望 DP 搞搞搞就结束了，然后发现直接假掉了。

愤怒了！

那只好尝试维护概率了。但是又搞出来一大坨感觉不大好做的 DP 形状，浏览了一下 T2 和 T3 仍然没有思路，回来继续看 T1，尝试放弃直接暴力维护总和和对应所有子节点的概率然后暴力转移，尝试推一点容斥的式子，发现好像没有什么用，完全没法放上去。

换个思路，看看能不能把其他总和算出来，总之就是尝试先用背包算出来总和分布，然后倒推扔掉某个元素然后和这个节点的长度分布去算出这个节点每个长度被选的概率。由于没学过“退背包”或者说“撤销背包”，场上认定这个东西不可做，最终选择了前后缀拼接的方法去做。

想完了，写写写！怎么写挂了。调调调。

终于写完了。前六个样例过了，然后第七个跑得飞慢，看了看决定改成线性预处理逆元——前面每次算一遍逆元时间真的爆炸了，经过苦难的调试代码环节，终于跑进了 1.2s！

剩下的无能为力，交给 CCF 神机。

剩下的一个半多小时开始火热冲击后两题的暴力，写完了，还剩半个多小时，T3 的大数据写了个神秘东西骗分，T2 的部分分也想到了，在最后半个小时全力冲刺最终未能成功只好遗憾离场。

DAY1：[64,100]+15+12?

DAY2

两道交互题一道超级长的神秘题吓哭了。

冷静下来觉得 T1 看起来不难，尝试用 \log N 的复杂度去找一下 0 但是后面就不会了。

机房某个神犇曾经讲过：

没这思维能力就别瞎摆豁你那猜结论了
使用 cnoi 办法找找规律早过了

于是开始写神秘搜索，爆搜了一下一定长度下所有的排列的区间 mex 然后用 Hash 统计了一下，发现了 mex Hash 相同的 mex 形如阶梯状物。

发现先二分找 0 然后再用二分每次找阶梯是带个 \log 的，所以猜测有某种线性的做法，机缘巧合下蒙到了一次 [0,n-2] 的区间操作然后发现这样就可以直接确定最右侧的数字了——因为缺掉了这个数字 mex 会直接变成这个数字。

经过大力推广发现只需要在一侧每次查询 [0,i] 从右往左直到找到 0 然后剩下的部分在另一侧再做一遍就可以了。大胆猜了一个结论：只需要管这些阶梯边缘 mex 变化的关键数字就可以了，剩下的只需要每个都满足大于其右侧的阶梯数字就可以了，到这里基本差不多了，直接上贪心，写写写。

过了！看了下时间还有三分之二。我还疑惑为什么省选会放一个绿题进来

T2 完全没思路，开始疯狂拼 T3 暴力。这 T3 的暴力是真难写吧，24 的分数硬是给我干出来了 4.5K 的代码长度，包括但不限于大分讨，全套的树剖 LCA，一套完整的 comp 逻辑，暴力还跑的慢的要命，一看发现我获得一个元素的排名用了带 \log 的 sort，但是实际上可以每个元素都比一遍得到不到 \log 的做法。

请输入文本。

总之在经过一亿次写挂以后终于拼出来了那 24 分，剩下的时间看 T2，猜了个神秘结论骗分但是编不出构造方案而且到第三个样例就开始大爆炸了。

真的要开摆了，剩下的时间拼分都拼不明白，还好马上就结束了……

不对，怎么有人进来说延迟 15 分钟结束？

没办法了，开始整活吧。

Noi Linux 没有中文输入法，用题面 PDF 中摘取中文文字勉强拼了一些。也许有人能在 2026 联合省选迷惑行为中看到我，但是那就是另外一回事了

出来发现 T2 的 n=8 可以线性基。

没复习线性基导致的。倒闭了

DAY2:100+[0,3)+24

D1T1 数据怎么这么水给我放过去了？

拿官方数据自测了一下，大概是 100+15+4+100+0+24=243。T3 暴力挂了。

距离进队还差 inf 分。