【番外】NOIP2025游记

· · 生活·游记

一言以蔽之，也是重温了一下为解决题目而深入思考的快乐吧。

赛前大约一周打了场阳间时间 CF，发现 FG 是两道逆天题，F 奋战 1h 后莫名其妙地调参调出来个方案，最后好像和官解殊途同归，官解是从分层推出合适的基数，我是直接考虑分成三层。然后 G 题你是认真的？FG 两道人类智慧。H 看完题后就忘记了只需要输出 2000 个方案即可，还按计数题在考虑多维 dp，我就说单峰和排列图这两个东西怎么能放到一起考虑。

开赛，稍加思索后 8min 秒了 A，然后看 B，画了画之后花了 50min 写出来了，有点困难，黑题说是。

现在是九点半，开 C，这么困难。手搓样例并思考良久后大概想到了填数的大概形态，然后考虑树上 dp，考虑了很多种方案发现都不太行，因为总是需要二维，然后复杂度就爆了。

然后开始调整思路，想到了转而考虑每个位置对祖先答案的贡献次数，然后将要求的贡献次数作为状态，画了画发现还是维护不了，又对着这个树的形态苦思良久后想到了应该是一个对树剖方案的规划，然后答案是每个点的树上前缀最大值。之后用了一些神秘的方式实现了一个树上二维 dp 的方案，但有一步转移时需要对每一个位置都在树上 dfs 一遍，然后复杂度就 O(nm^2) 了，其中有一个 nm 是所有节点的子树大小和，可以拿到 76 分，之后没有想到能怎么优化就扔了，感觉整个 dfs 过程根本没有重复的状态，所以又随便在 dfs 上加了点剪枝就扔了。

赛后听别人讲的好像正解就是拿三维 dp 优化状态数做的，有点难绷，但感觉和我的做法本质相同，正解的减状态数好像也和我的剪枝本质差不多？但他们说的数据结构优化就不知道是啥了。n = 4000,m = 80 的大样例都跑了 0.1s，应该还是不太能过吧，造个若干条链复杂度就卡满了，可能缩一下二度点能解决，但赛时已经没时间写了。当时也猜到可能方向错了，但都写到这了也无路可退了。

做到这又花了 1.5h，现在是十一点，还有 2h，开 D，但感觉不可做啊，单看题目格式长得像是个去年 CSPT4 和 NOIPT4 的杂交版。

想了想没思路，又想了想想出个分治，虽然带 \log 但开始莽，不是说 CCF 机子快吗。写完后最后一个大样例 4s，之后观察特殊性质想到个给短的区间打表，这样我如果给 2^k 以下的长度打好了分开考虑，我就可以少分治 k 层，平衡一下发现空间开不下（

管那么多干啥，阈值小点就是了。不难发现可以只用排序的单 \log 求出一个固定区间长度的每个位置答案，具体把每个区间和从大到小往里覆盖然后拿并查集记一下就行了。然后发现要想查询区间 \max 有点烦，但如果问的都小于阈值那直接分治一遍也未尝不可，所以变成了只需要后缀 \max，然后就舒服了。

但为什么还是跑了 3.8s。最后还有点时间用基数排序替换了带 \log 的排序，变成了严格 O(nB) 的预处理，变成了 3.6s。就是这样了，如果 CCF 的评测机速度能达到北师大实验的两倍就过了。但不管怎样前 75 不能拿不到吧，北师大实验的机子都只用 2s。

右边是 cxy（不知道网名），发现他原来已经高一了而不是初三，据他说他 T4 打的单 \log 出了个很离谱的错误，改过来后最后一秒没交上，尝试理解他说的线段树做法未果。他说他 T3 好像会但没写，也写的是 O(nm^2)。

之后下楼遇到 le0n，果然 AK 了，询问了 T3 做法，大致理解了，在前文已有提及。之后尝试理解 T4 做法未果。省流：问了很多人但啥也没听懂。

总之现在是 100 + 100 + (76 + eps) + [75 - eps , 100]？

刚出考场的时候再群里发的估分是 100 + 100 + 76 + 60，因为我以为 T4 一个点 4 分。

然后是吃午饭并无缝衔接回到学校上课。

所以全世界就我 T3 写了个二维 dp 吗。

所以这次 AK 的人是不是跟去年差不多？那就是我确实变弱了。之后看懂了 T4，好像确实不难，但也确实是个没见过的 trick。

最后留一道题，是我赛前在观察 emacs 的 zone-out 的时候想到并解决的：

有 n 摞箱子，第 i 摞有 a_i 个，每次操作随机一个箱子，如果它在所在摞的最上面就拿走它，否则无事发生，求期望需要多少次操作才能拿走所有箱子。

答案很简单，可以在评论区发一下。