NOIP 2024 游记

· · 生活·游记

考前没有训练也没有复习，那就随便写点考试经历吧。

开考，刚读完题电脑就死机了，换了一台电脑，敲完缺省源又死机了。趁着调电脑的十五分钟想了想 t1，最开始以为 sort 一下就结束了，后来才发现伪的彻头彻尾。不过 t1 毕竟不会太难，我并没有尝试一些太复杂的想法，很快也顺利地想到了用贪心，于是电脑重启之后十分钟就写完了。

再看 t2，发现是个很简单的计数，写起来也很短。大概九点零几分的时候就过了两道题目的大样例，这时我注意到右边的龙队好像也刚写完两题，感觉当前速度保持得很好啊。想到时间比较充裕，我打算晚点写拍，先去看后两题。

最开始以为 t3 的关键边是相互独立的，心想那 O(nk) 不是有手就行吗。后来才发现一棵树可以被多条关键边同时生成，不过容斥一下 k \leq 8 应该还是好做的。思考图的本质，它的每个点双连通分量都是完全图，而完全图的 dfs 树必定是一条链，那么只需计算每条链有多少种可能的起点与终点就好。这样看来，A B 性质都是显然的，数一数已经 64 分了，正解应该不会太难。

然后就是经典的低头想题，抬头发现已经十一点了。不过也大致胡出来了一个利用树形 dp 进行容斥的做法，因为如果一个点双中钦定了三个起点，那必定没有合法的方案，这样就只用容斥两层了。边写边调，大概到十一点五十左右过了两个小样例。一测大样例发现 RE 了，心率立刻就上来了，时间只剩下一个小时，必须做出选择。

决定再调二十分钟，调不出来就放弃。再一测，怎么连链和菊花都 RE 了，那必不可能是 dp 写挂了啊！又注释掉了一大半的代码，发现 dfs 几次就 RE 了。绝对是 dfs 爆栈了！可是四个月没打模拟赛了，我早就忘记把栈空间开大的指令了，这意味着本题的调试没法再进行下去了。眼看着已经十二点多了，我只好删掉想了三个小时的正解代码，去打暴力保住大局。

大概十二点半左右就写完了 t3 的 64 分，又花了十分钟写完了 t4 的 O(n ^ 2)，算下来应该是 100 + 100 + 64 + 20 = 284，可能勉强上队线吧。最后十几分钟在检查前两题的代码，可惜没时间写拍了，肉眼看了看没问题就交了。

出考场后问了一圈没问到 300+ 的，感觉这个分应该还有救。再一问，怎么大家 t4 分都这么高？重新想了想，忽然发现 \operatorname{LCA*}(l, r) 就等于 \min_{l \leq i < r} \operatorname{dep}_{\operatorname{LCA}(i, i + 1)}，转化之后就直接和树无关了。这样看来，好像有 60 多分都是送的啊，输麻了！

第二天凭记忆写了写四道题的代码，也确实拿到了 284 分，这说明思路是对的。现在只能祈祷考场上没写 typo，不然就重现 NOIP 2022 了 /ll

总结下来还是挺失败的一场 NOIP，不过鉴于完全没备考，或许没崩掉已经是万幸了吧。