NOIP 2025 游记

上一篇游记还是第一次参加 CSP-S，今年大概是最后一次 NOIP 了，再来写一篇。下面也简单回忆了一下这两年。
Day -1

早上不去学校了，下午抵达高级中学高中园附近的酒店。
Day 0

根本没有这一天，Day -1 就是周五。如果把周五定成 Day 0 又有一种这天很重要的错觉。
Day 1

前往考场。这学校的大门到底在哪层，为什么我看到了四五个楼层后才到 3F？？
8：27 解压，眼花了把 : 看成 i。
先开 T1，想到把一个 \(x_i\) 和一个 \(y_i\) 绑到一起后容易发现只有 \(x+y\) 最小的有可能买超过一个，然后按 \(x\) 排序贪心即可。
五分钟，优势在我。这不比什么 duel/edit/club 简单多了。
再看 T2，一开始看成求什么 \(w\) 可以贪出所有 \(w\) 贪出的最大值（我觉得这肯定是题面的问题，不只是我个人理解有问题）。突然又反应过来这个贪心是背包的经典假做法，再看样例才反应过来问的就是这个贪心什么时候能求出背包的最优解。
接下来就没什么思路了，一直在各个部分分横跳。差不多一小时的时候冷静下来，发现考虑出错的情况，一定是选了的性价比最小的两个 \(1\) 原价加起来比没选的性价比最大的 \(2\) 原价低，而且倒数第二个 \(1\) 性价比比这个 \(2\) 高。
考虑枚举倒数第二个 \(1\)，它一定是占用了第 \(m-1\) 个位置，然后再枚举没选的性价比最大的 \(2\)，式子里有一个形如 \(\sum_i\binom{A}{C-i}\binom{B}{i}\) 的部分，当时没想清楚这是不是范德蒙德卷积，以为只有 \(\sum_i\binom{A}{i}\binom{B}{i}=\sum_i\binom{A}{A-i}\binom{B}{i}\) 能范。
先写了 \(\mathcal O(n^3)\)，没过第二个样例。红温，难道连 NOIP T2 都做不出来了。这第二个样例 \(a\) 还这么大。
这时思考了一下组合意义，发现上面那个确实是范德蒙德卷积，同时发现一个细节错误。怎么输出结果误差更大了？
仔细研究了一下样例二，发现结论有问题，倒数第二个 \(1\) 并不一定占用 \(m-1\)，有可能后面跟了一些 \(2\)，再以一个 \(1\) 结尾。稍微改一下终于过了。
一个半小时过两题，感觉不妙。
接下来 T3，看完题面和数据范围立刻设计了一个 dp：\(f_{i,j}\) 表示点 \(i\) 的字数内，mex 为 \(j\)，最多剩余自由点个数。写完费了些力气优化到 \(O(nm)\)，输出答案时反应过来这和答案有什么关系？？
喝完一瓶水冷静一下。手玩了一会，发现可以考虑每个点的 mex 从哪个儿子继承过来。在树上取出一些不相交的祖先后代链，设 \(d_i\) 表示点 \(i\) 到它所在链顶的点数，如果 \(i\) 不在一条链上则为所有祖先的 \(d\) 的最大值，答案即为所有 \(d\) 之和。
其实一开始对着小样例我以为不在链上的 \(i\) 的 \(d\) 是直接继承父节点的 \(d\)，这样直接 dp 是 \(\mathcal O(nm)\)，写完样例 3 和 5 错了，然后想到上面的结论变成了 \(\mathcal O(nm^2)\)。
由于这个 dp 还要开 vector 以避免 MLE，所以我不想直接写。接下来我一直想着去推更多性质，没有尝试去直接对着上面的 dp 优化（这可能是因为没有写代码，这里真心建议大家多去实现部分分，说不定写着写着就能拿更多分了）。
期间看了一下 T4，会了 \(\mathcal O(n^2)\)，AB 性质。这 DE 是什么？
12 点整，只有两百分，34 全不会，今年 NOIP？？

喝完第二瓶水冷静一下，还是觉得现在这个 T4 分数放在 NOIP 不合适。考虑枚举 \(i,r\)，如果 \(r