福建联合省选 2026 勉强进队记

· · 生活·游记

警告：写在凌晨，精神状态很差！慎重阅读！

NOI 2025 到考前我进行了 0 次训练。

为了扭转颓势，我在考前和一位关系很好的同学联机玩了一天游戏，状态好多了喵！

[Day 1]

看完 T1 基本就会了，对于每个节点求出子树所在重链的长度的分布列就行了。

写的时候发现复杂度不是很对，怎么办呢，我想了很久发现可以特殊处理重儿子。

我太久没训练了，证明了好久复杂度！

由于我太久没写代码了所以做了 1h，有点慌。

T2 感觉是个乱搞题，很痛苦的做了 3.75h。

T3 来不及了，写个必要不充分的条件尝试骗第一档分，不幸只有 4 分。

总分 100 + 80 + 4 = 184，丢人欸。

[Day 2]

我原以为 Day 1 打得已经很搞笑了，没想到 Day 2 将我小丑的一面毫无保留地呈现了出来。

看完 T1 5min 写完 5min 调完，这个东西我在至少 3 个地方看到过。

T2…猜了个结论…和答案误差不超过 3！然后调一调就做出了 25 分…这个时候 0.5h 了。

然后感觉构造要分四类讨论，以我的代码能力肯定写不出来！

所以我仔细思考，发现应该 n>k+2 的时候要归纳。

为了减小代码量，我又写 + 思考了半个小时，想出了简单的构造并实现。

由于我比较胆小，写的时候一直注意操作次数爆没爆炸，重大失误啊！训练太少了。 怎么办，2.5h 大战 t3，这可能吗？ 我先 0.5h 胡了一个一个人的算术 + 换根 + 二分的解决 $o_x\times o_y=0$ 的解法。 我发现，可以先按照子树最大深度排序，这样就不用动态调整编号了，我快快写完了。 这个时候，换根太难写了！我写了一个暴力，但是它成功在 1s 内解决了 #1 以外的所有点。 还剩 1h 的时候，我已经解决了 $o_x=o_y=0$。 好，我们来写第二部分，拼了一车 DS，再加两个单调性，64 到手。 这个时候，我 -fsanitize 了一下，发现我内存泄露了，要泄露就露点算了，反正 MLE 不了，因为我 new 完没有删除。 我通过了 64 分，只剩下 15min 了，怎么办？？？加时 15min！ 加时真是太好了，我发现这样我可以有时间写复杂度正确的换根，这是因为我怕 $o_x=0$ 或 $o_y=0$ 的部分分的 down 和 data 不是同一个 gen。 要是早知道 data 这么水，我肯定 5min 滚完菊花了，这是本场比赛最大失误，让我少了 $4$ 分，可恶啊！ 但是，我 30min 居然没写完这个换根！只能匆匆检查一下结尾了。 要是没有加时，给了我虚伪的希望，我就能过菊花了（心虚），可恶啊。 输在了不会经典题目和熟练程度上！生气了！ $100 + 100 + 64 = 264$，好像没那么丢人了，但是还是生气！因为我不会树分块！我必须承认这是我实力严重不足的体现，也是半年训练的搁置所应得的！ ### 总结 - Day1T1：中规中矩模板化的树形 dp（极常见算法），唯一难点是对大小分治讨论（考察频率较低）决定使用暴力树上背包卷积（极常见技巧）还是撤销背包（即多项式除法，较常见技巧，难度中等）； - Day1T2：非常奇怪的题，各种各样的乱搞纷纷通过了此题，考察了选手的乱搞水平和搜索剪枝水平； - Day1T3：转化到环上后（小思维，较容易想到）后套路化的数学分析和构造（较繁琐，不易想明白，代码实现复杂），后半部分整体较为机械化且平凡无聊，但是需要注意复杂度（这个题有两种写法，想清楚再写会好一些）； - Day2T1：trick mex(a[l,r])=min(a[1,l),a(r,n])（trick，出现次数中等，比如梦熊挑战赛出现过，CF Interactive MEX Tree，等等，国外比赛曾在签到题位置出现，场上也有机会想到），注意到这个事实后只需要关心前后缀，随便构造一下就好了（很清新，不难写），这个题放在三年前可能算思维题，现在出烂大街了； - Day2T2：数学题，大胆猜出必要条件后数学归纳法构造，构造方法很机械（繁琐程度中等），代表元缩减构造元素的技巧也很经典（在构造中极其常见），在数学竞赛中经常数学，本题中使用一部分线性代数结论（简单）可以更快排除干扰项，但是不好给出直接构造（即存在性证明，或辅助完成题目结论猜想或者降低部分难度），这道题写之前想清楚可以大大降低代码难度，不然就得分四类讨论了； - Day2T3：偏二合一。第一部分类似 luogu 一个人的算数（湖北省选模拟，经典题），但是直接写过于复杂且换根繁琐，需要用到一些简单观察辅助代码编写，减小代码量（这个观察以前没有出现，比较个性化，不过不难）；第二部分需要分四类讨论，第一类可以使用换根的思想解决（不太寻常的换根用法，不能直接背代码，不过理解了就很快想到），第二类第三类只需注意到单调性（较易）即可，第四类比较繁杂但是很经典，需要使用树分块（较难算法，出现次数不高），处理也比较机械，但是我不会。本题需要高超的代码能力。 总结： - 这场比赛比较考验省选 / NOI 难度的基本功，很多题目（D1T3, D2T2, D2T3）都是比较复杂的推理，但是每一步都比较直线，分叉不多； - 除 D1T2 以外的题目都很按部就班，做法偏机械化，应用也不是很灵活，但是应用较深，需要对算法有着**熟练**的理解，也没有什么小巧思，繁而不难； - 同时，本场题目代码量（D1T3, D2T2, D2T3）较大，想清楚再写可以降低代码难度； - 大部分技巧都在以往见过（除 D1T2），部分题目（D1T1, D2T3）需要一点点变通； - D2T2 数学题，虽然技巧没有直接出现但是方法是确定的； - 除 D2T3 外，算法均在提高范围内。