联和省选 2026 游记

Day 0

还记的上次试机是因为换系统了……

这次试机本以为只是试机，结果题目上面居然不是 $\large A+B$ ，而是大大的 $\large FILL$ 。我推了 1 个小时连 $n=2$ 都不会写，最后跟我说要用那个引理……

还好省选不会再考这个我学都没学的东西了……

Day 1

一看 T1 居然是一个期望题目，耗费了 1 个小时推样例没有退出来，换下一题。

T2 还是很良心的，给了 $15$ 分暴力，剩下的推了一会儿性质 A ，写完后就有了 $30$ 分啦！

看到 T3 ，没想到省选还会有 SpecailJudge 。甚至输出 Yes 和 No 都有 $50\%$ 的分数，或许今天就有 100 分了？

哼唧哼唧推了 1 小时，结果发现自己连 Yes 和 No 都不会，这题还是太难了，只能打完暴力走了。

T2T3 太难了！

最后一个多小时回看 T1 ，发现求轻边数量的期望和求某条边是重儿子的概率是等价的，十分兴奋的以为自己 Day1 就要切题目了，结果最后发现自己不会算概率，最后黯然离场……

估计 8+30+12=50 。

Day 2

今天文件一下发我周围的人都吸了一口气（不知道为什么），然后看了所有题目，结果 T1T2 都是交互，只有 T3 正常。平时没有怎么写交互，就先开 T3 了……

苦思冥想 T3 的结果就是这题目完全不是人出的（为什么会有这样的集合（ $\{\varnothing , \varnothing,\{\varnothing,\{\varnothing\}\}\}$ ）！），甚至连 $n \le 20$ 的暴力也不会，只能看 T1 。

T1 就还好，一开始只想拿到 $n \le 10$ ，于是硬编码，先找 $0$ ，再找 $1$ ……写到找 $2$ 就发现硬编码复杂度太高，分类讨论太多，正想放弃时突然发现这个可以写成循环，因为如果第三次找到的数字 $>2$ ，那么中间所有数字都可以直接忽略，任意排列。想到这个就直接开些，过了样例 1 后在 $n=100$ 的样例 2 上查询了整整 $261$ 次，拿到了 $3.8$ 分的高分。本想着优化，结果突然发现找数字的过程可以二分（我一开始写的是循环暴力找，复杂度高且查询会有重复），一口气给 $261$ 降到了 $103$ ，拿了 $4.8$ 分！但是这样还是会重复查询同一个区间，于是用一个 $map$ 记录一下，直接降到了 $99$ 次！比他给定的还低！但是这样时间还是 $O(n\log n+n^2)$ 的（因为我后面是暴力赋值）。但是我前面都能二分，赋值为什么不能二分？改一下就是 $O(n \log^2n+\log n)$ 的时间了，通过 $3 \times 10^4$ 绰绰有余。

切掉 T1 后看 T2 一脸懵，想了半天也没能想到暴力怎么打， $k=3$ 怎么写。只能继续看 T3 。

此时离考试结束还有 3 个小时左右，认真看了 T3 数据范围后发现 $r=1$ 时只有 $x=y$ 才能计数，简单分类一下就行。性质 $A$ 是菊花图，关键的节点只有一个，分类讨论更多一些，也还好，一下就通过了大样例， $8$ 分到手！

剩下时间不是在推 T2 的暴力和 $k=3$ 就是在想 T3 的暴力和 $o_x=o_y=0$ ，最后到了考试结束，这四个东西我一个也没有推出来。

$13:20$ ，本以为一切结束了，结果考试时间突然宣布延长至 $13:45$ （因为 T3 样例 2 的解释中途修改了两次，最后一次离考试结束比较近，虽然不知道 T3 样例 2 的解释有什么用），只能坐牢 $25$ 分钟。

估计 100+0+8=108 。

后记

挂完了。