2026 省选游记

· · 生活·游记

Day 1

T1 首先发现答案即为：每一条边为轻边的概率乘其子树大小，考虑求每一条边为轻边的概率。不能直接求重链长度期望来算，所以设 f_{x,i} 为节点 x 重链长度为 i 的概率。然后发现有一个求和的式子，开心地搞了一个背包。又发现要去掉当前节点，还要回退（/bushi）然后就 O(n^3)，不会优化，跑了。

开 T2，打了个暴力，B 性质写了个假做法，设了个阈值，但是忘记调参了，应该会挂分。

大概 48+20=68 爆炸。

Day 2

好了，两道交互题。

T1 直接魔改了一下交换代码，然后通过观察，发现只是要找寻所有对 l,r，满足 l,r 是最短包含 [0,x] 的区间，每一个区间都会对 [0,x] 的值的位置添加限制，其中对 x 有更强的限制（应注意），用个线段树维护限制，最后把所有限制提取出来，发现是一个区间覆盖，按右端点排序填写，再用链表优化一下即可。

调试太久了，交互库 O(n^3) 一度让我以为是我的代码 TLE 了，结果调试 40min+。

然后 T2 感觉可以模拟退火，结果没时间写了。。。

同学们都考得这么好啊啊啊。

星图铺就的，即是归途。
有人循着它，便迷了路。
我该停留在哪里？我问我自己。

——归去，也无风雨也无晴。