联合省选 2026 游记

· · 生活·游记

Day-1

来到考场附近的酒店。

破了一晚上防。

Day1

很早来到考场，面到了 wmrqwq/xin。

然后和上次见面还是退役前的机房同学聊了聊。

开考。T1 好像有难度啊。十几分钟想出来一个 dp 修修补补没改出来。

已经过了快两个小时了。花了 1h 打了后两题暴力。

最后做 T1。依旧没有结果。维护某个节点除掉一个节点外其他子节点所在重链长度和的期望不会做啊。是不是要贝叶斯公式。那倒闭了。

Day1 炸成这样，没啥心态了。回酒店写了两个简单题，略微复健了一下。 ## Day2 基本不抱什么希望了。 开考前唯一的印象是《字符“扭一扭”》。一看题，怎么两个非传统？？？准备倒闭了。 浏览了一遍题，决定先做 T3。分讨了 $26$ 种情况，把菊花图解决掉了，又写了个树上差分解决了 $r=1$。 此时开考一个多小时了，得分只有 $0+0+8$。 有点急了，回去开 T1。先看出来了 A 性质怎么做。当 $\operatorname{mex}$ 发生变化的时候，一定加了个数等于这个 $\operatorname{mex}$。这样还有数没放完，但是没放完的数一定不会在任何区间内成为 $\operatorname{mex}$，所以从小到大放一定对。 很快写完了。$8+0+8$。 进一步地，发现可以往左往右二分找下一个数，这样子处理完记录每一次左右端点移动的长度，最后从小到大填数。前面扫一遍找 $0$，次数 $n+n \log n$。忘记多少分了，大概有 $40$ 分。 然后写了一个 T2 的 $k=3$ 求答案，维护度数过了样例，但是推广没成功。 然后继续优化 T1。先把找 $0$ 改成递归，进一步地发现处理出前后缀，在这个结构上二分是可以的，因为有一边加再多都没贡献，因为下一个数在另一边。但是更新答案需要再查一次。同时发现前缀 $n-1$ 和后缀 $0$ 都为 $n$。这样就是 $2n+\log n-1$ 次。 接着再去写后两题。不是很能想出来，T3 写了一个记 $l_u$ 表示 $u$ 到叶子的距离，$w_u=\sum_{v \in G_u}\dfrac{w_v}{2}+l_v$，双关键字比较 $(l_u,w_u)$，过了 $10$ 的样例。T2 写了一个模拟退火过了 $n \leq 8$。 估了一下总分（T1 乱估了一个界），大概 $[80.42,?]+[3,11]+[8,24]$？不知道会不会比 NOIP 高。 出考场才知道 T1 $0$ 可以直接倒着查前缀找分界点，刚好多一次少一个 $\log$。注意到加数 $\operatorname{mex}$ 只增不减，左端点的后缀和右端点的前缀取 $\min$ 就可以查出来区间 $\operatorname{mex}$ 了。那我写的 8KB 算什么。