NOIP 2024 游记

开 T1，感觉随便贪就对了？简单证明了一下，每次考虑第一个被 ban 掉的点之前的贡献，看起来确实是对的。首先照着这个证明的思路写了一个类似双指针的东西，实现起来有点繁琐，写了一半弃了，最后按照最开始的思路写了一个逐位贪心，半个小时的时候过了大样例。

T2 看起来也很简单，随便推下式子就做完了。又过了半个小时，优势在我。

开 T3，想了四五十分钟，感觉直接 dp 就是可行的，记 $f_{u, 0/1}$ 表示 $u$ 子树内是否有可行起点的方案数，转移时做一些容斥即可。当时觉得这个转移时的容斥是简单的，结果写完了之后 $k=1$ 的大样例过不去。调了半小时，把容斥改成了一个 $2\times 2$ 的背包，$k=1$ 的大样例过了，结果 $k=2$ 又死活过不去。又调了一段时间，一看只剩下 1.5h 了，T4 时间要不够了，但是感觉我的做法一点问题都没有，于是决定继续调。最后发现这个背包必须再加一维，改了一个 $2\times2\times2$ 的背包，终于通过了大样例，但是 T4 只剩下 1h 了。btw 这个背包的三维表示的分别是选择了几个链的端点、有几个端点的子树内有可行起点且子树内的链不全有端点指向父亲、有几个端点的子树内有可行起点且子树内的链都有端点指向父亲。出来问了一圈没有写的像我这么依托的。

T4 想了 10min 会 2log 了，类似链，枚举 lca 深度，用启发式合并维护每个点在哪个 lca 的子树内，询问时二分，查询区间内最长的同色连续段即可，可以用可持久化线段树或整体二分实现。又想了 5min，由于序列上颜色段的合并只会发生 $O(n)$ 次，前面启发式合并部分的复杂度可以优化到 $O(n\log n)$，当时想到这就感觉全对了，以为自己会做 1log 了，但是后面的二分并没有去掉，复杂度还是 2log。还剩下 45min，按道理来说这么紧张的时间应当去写点部分分，毕竟 T4 的部分分非常多。但是场上鬼使神差的决定去冲我所认为的正解，事实上这玩意既难写常数又大，写出来了怕是也没什么分。快速 rush 了一个可持久化线段树，启发式合并实现到一半就发现这东西不可写了，此时还剩下十多分钟，放弃了，写了一个 B 性质，在交卷之前过了编，样例都没测。不过我现在想起来我输出的是 lca 而不是 lca 的深度，所以这个题就一分没有了。7k 代码获得了 0pts 的好成绩。事实上仔细想了一下当时已经实现了的代码离 2log 做法也就几行代码的距离，总之场上脑子完全就坏掉了，能写个大常数 2log 其实也挺好的。

预期得分：100 + 100 + 100 + 0 = 300。

希望别挂吧，挂了我就寄了，NOIP 2024 充满了失望。

---

upd 2024.12.6: 没挂分，挺好的。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。