联合省选 2026 游记

· · 生活·游记

Day 1

开场通读题面。后面两题数据范围也太奇怪了。

选择了正序开题。一开始以为要对每个叶子求出答案，想了一下不太能做，仔细看了一下发现是求答案总和。那应该是往拆贡献的方向上转化一下，把贡献拆到重儿子上，感觉一下大概有一个背包做法。

写了一个直接记录重链长度和进行转移的背包，想把重儿子长度的贡献直接塞到背包里。后来发现好像必须要记录重儿子的长度，于是改成了分治的 O(Tn^2\log n) 做法。其实这里也想过退背包的做法，但感受了一下以为要除 0，没细想。

写完大概是 1h15min，发现大样例跑了 0.6s 就扔了，感觉带 log 应该不会被卡很多分。

然后去想 T2。花了 30min 想了一个枚举答案后 dp 的做法，算了一下感觉复杂度是 O(n^2kans) 的，并且感觉存在 bitset 优化的潜力。

花了大概一个小时实现了这个东西，原因大概在于这个东西开不下记录转移点的数组，于是构造方案特别难写。写完发现过不去第二个样例，看了一下发现是因为答案太大了。这个时候突然发现把复杂度算错了，其实是 O(nk(ans)^2) 的，并且完全开不下。

这个时候大概是 3h，我意识到这场考试可能完全倒闭了。感觉还是应该看一下 T3，不过这个时候已经没办法正常思考了，花了 1h 拿下暴力分。

然后回来给 T2 拼分。但是又花费 30min 搓出了一个假做法！发现我一直在对长度的可达性进行 dp，但好像直接 dp 最小长度就行。然后就有 O(nk^2) 做法了，但是考试还剩大概 20min。

最后卡了一下 T1 常数，大样例跑了 0.3s。

100+15+16=131。

Day2

开场通读题面。怎么前两题都是交互啊。T3 感觉是很麻烦的题。

还是正着开题。T1 感觉先把 0 的位置找到，然后问一下前后缀最大值再随便构造一下就有 n+\log n 次的做法，然后找 0 直接用前后缀信息找就是 n 次的。大概 40min 写完，拿 n=10 的全排列拍了一下就扔了。

开 T2。求答案的分好像不太多，感觉可能比较简单。找了 deg 奇偶性的上界和边数奇偶性的上界，发现 starmap3/5/8.in 各有一个点比答案少 2。2h 左右决定先不管，去看一下 T3。

花了一段时间读懂 T3 题面。发现树随机的情况分很多，于是写了一个期望复杂度比较对的比较，大概能过 n\le 2000。决定冲一下 n\le 10^5，大概要写一颗平衡树+换根。在 3h30min 的时候仍然没调出来，因为 T2 之后的部分还没怎么想，于是拼上 r\le 2 就弃掉了。

回来看 T2，发现大概是 k\bmod 4=1 的时候存在一些特殊情况，判掉之后反正是把大样例过了。拼上了 k\le 3 的 9pts，又给 n\le 8 编了个假做法，发现样例都跑不过就删了。

最后又延时了 15min，但可能也没干什么事。

100+34+32=166。

总分是 100+15+16+100+34+32=297，成功用 Day 1 的搞笑分数把 NOIP 的优势全部消耗完了。

希望 NOI 发挥别太幽默。