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_ibinom{A}{C-i}binom{B}{i}) 的部分，当时没想清楚这是不是范德蒙德卷积，以为只有 (sum_ibinom{A}{i}binom{B}{i}=sum_ibinom{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<i+L)，那么 (l)（这里考虑的区间是 ((l,r])）就不用受 (l<i) 限制了，只需要考虑 (lin[r-R,r-L])。(lgeq i-L) 同理。这两部分容易四次单调队列求出，然后只需要考虑 (l< i-Lwedge i+Lleq r)，直接令 (Lleftarrow 2L) 递归做，复杂度 (mathcal O(Qnlogfrac{R}{L}))。十二点三十写完，能拿一些分。

回去写 T3 (mathcal O(nm^2))，四十写完。其实也就十分钟，所以还是应该早点写的。

不能放弃，T4 再进一步：如果 (rleq R) 或 (lgeq n-R)，就不用考虑 (R) 的限制，结合上面也可单调队列做。然后只用考虑 (l<n-Rwedge r>R)，故可以令 (Lleftarrow 2R-n)，这样可以过 C 性质。

十二点五十拿完 T3 和 T4 所有部分分，时间也差不多了，没有更多进展了。

预估 (100+100+76+75=351)，平心而论不算差，但感觉和上一个赛季比总归是差了点。后面两题都没做出来还是有些遗憾。

连续三年 CSP 400，NOIP 却是奥利奥。

总的来看，在快速切其他题，后面时间全给最后一题时我通常会发挥最好，否则一旦僵持在两题之间，结局基本就是都做不出来。

• CSP-S 2024：前三题白给，最终做出 T4。
• NOIP 2024：前两题白给。先看 T4 一步就想出来，剩下时间做出 T3。
• 25 省选 Day1：T1 白给。追忆想了个多个 (log) 的做法，先当部分分写，无压力通过。最后 T3 拿了 (52)（对我来说很高了，赛后看题解会不了一点）。
• 省选 Day2：其实这次没做出 T2 只有 (64)，T3 部分分就出了点问题，不过说实话前面已经够了，后面两题就算都没分也有省队。
• NOI 2025 Day1：三个小时前两题。T3 先搞了个用哈希的 A 性质，写完感觉进制哈希太丑了换了个异或哈希，没想到 selfeval 一交过了没有性质的点，然后随便改改就 (80) 了。
• NOI Day2：T1 一个小时搓了个十一个数组的线段树（说实话我觉得这题挺难的）。T2 被集合幂级数肘了，没想到 (2^{|Scap T|}=frac{2^{|S|}times2^{|T|}}{2^{|Scup T|}})，写了个 (mathcal O(3^nn)) 有 (36)。T3 拿了 (35) 做出了无比正确的决定，回到 T2 卡常卡到 (56)，这才有了金牌。
• CSP-S 2025：也是先写了前三题。T2 复杂度丑了，T3 代码丑了。不过这个 T4 其实也不难。
• NOIP 2023：做完前两题后一直磕 T3，也只有 (70)（然后因为数错数据点子任务分治挂了 (5) 分），最后才给 T4 拼了点暴力，没发现是个简单的数据结构优化 dp。
• 24 省选 Day1：季风没用到 __int128。T2 直接暴力过 (72)，这特殊性质纯提示性+观赏性？
• 24 省选 Day2：三题都不会。2 小时 T1 假了。2 小时 T2 假了。总分两位数。Day 2 坠机。
• NOI 2024 Day1：后面两题都不会，勉强拼部分分上 (200)。
• NOI 2024 Day2：T1 只有 (50)。想到搜，没看大样例以为答案可以很大，感觉没多什么分就没想着写。剩下三小时 all in T2 的一个树剖 (mathcal O(nlog^2n)) 做法，没能调出来。总分 (100)。Day 2 坠机。
• NOIP 2025：如前文。

这样看来，其实这次还算好了，虽然两题僵持很红温，但至少 T3T4 部分分打满了，说明第六年确实是有进步的。

总结：有了部分分尽量去写，代码可以帮助理清思路，甚至带来意外收获。毕竟信息学竞赛最大的特点就是写代码，光对着草稿纸想那不成数学竞赛了吗？

Day 2

前往北京一周游。

怎么北京这么冷，而且下午五点就这么黑。坐个飞机好像坐穿越了。

气候条件还是深圳好。