NOIP 2025 游记

· · 生活·游记

前言

虽然我已经高一了，但这次是我第一次打 NOIP，碰到如此题目，感慨良多，特写一篇文章纪念我为期不长的 OI 生涯。

我初二才开始学 OI，但当我敲下第一行 C++ 代码时，这些在键盘间跳动的代码就成为了我为数不多的信仰。由于 whk 实在太菜，初三一整年都没有时间进行系统的训练，导致我在初三升高一的暑假才开始学习提高组的算法，在机房中应当算得上训练时长最短的一批了。也正因此，我对于今年的考试并没有抱太多的期望，更多的应该是明年再战了吧。

11.15——11.28 考前

经历 CSP-S 的大失败之后没多久，来不及感伤，我就投入了为期半个月的停课训练中。

我的实力应当是机房中最弱的一批了。考前的模拟赛密度、强度都很大，每次模拟赛，我似乎都久坐于电脑之前，苦思冥想，最后遗憾离场。

同机房的大佬们总是那么侃侃而谈，轻松解决掉我高攀不起的题目，着实令我羡慕。他们灵活的思维、巧妙的处理似乎永远遥不可及，就在这一次次的不甘中，我慢慢接受了自己的平庸。

不过，我也在这次训练中收获了许多。随着训练量的累积，我的模拟赛成绩有所上升（虽然不多），对于各类算法的理解和运用也有所进步。

就这样，我带着兴奋、忐忑又有一点恐惧的心理迈入了考场。

11.29 正赛

打开试题之后，首先通读四题，发现 T2 是最不擅长的计数，于是打算做完 T1 后先做 T3。

仔细读完 T1 题面，有了大致的思路。首先由于 m \le 10^{18}，背包是完全寄了，DP 感觉没啥道理，于是考虑如何贪心。一开始看特殊性质以为和 x,y 之间的大小关系有关，结果推了一会儿发现假了，才后知后觉的想到要找到最小的 x+y。（没救了）

接着我立马想到，这组 x+y 肯定尽量取，其余的取 1 个就好，于是转化为对 x 排序再求前缀和的问题。但我突然发现，假设当前枚举到 i，如果 y_i<x_{i+1}，那么显然对于物品 i，买多个比 1 个更优。

如果这组 i 的 x_i+y_i 最小，那么显然不必继续计算前缀和，因为后面的不会选到。若是这组 i 的 x_i+y_i 不是最小，那么这组以后也没必要选，因为后面的一定不会更优。

于是我计算这部分前缀和再枚举，计算最小的 x+y 组要买多少对答案取 \max 即可。

接着，我开始思考 T3。可能错误的开题顺序导致我遗漏了 T2 的部分分（这是真没救了），最终导致得到了较低的分数。

首先注意到了深度为 2 的特殊性质。考虑这种情况下树最多只有 3 层，因此可以直接构造最优解计算答案。先考虑最深的结点。假设以根的重儿子为根的子树大小为 k，那么叶子结点全赋为 0 的贡献与赋为 0,1,2,\dots,k-2 的贡献一致，于是可以求得这部分子树的贡献为 k+1。

然后考虑给根的其他子树赋值。假设刚才选取第二种赋值方案，那么重儿子的权值应为 k-1。显然，给根的其他儿子赋为 k,k+1,\dots 是最优的。至于根的其他子树中的叶子结点，全赋为 0 即可。于是最终得到了一个式子直接求得答案，测完对应的大样例对了，应该能获得 8 分。

然后，我就不会了……

硬着头皮逼自己思考，发现这题树形 DP 似乎略有点道理。推了很久的状转方程发现小样例都不对，感觉非常的倒闭。抬头看一眼时间发现已经 11:30 了！心态瞬爆，我不知道哪里用了这么多时间（没有时间观念真可以退役了），现在想想，可能 T1 就做了一个多小时？

在炸裂的心态中，我不想思考，去了趟厕所强制自己冷静下来。由于 T4 特殊性质很多，于是着手思考 T4。结果想了半天发现自己连 L=R 的特殊性质都不会！甚至，都没有想到用单调队列这一显然的方法维护答案。无奈，长考了接近 1h 后只好胡了个暴力上去，结果小样例又没过……调了半天都没调出来，索性直接放弃 T4。最后，当我想思考 T2 时，发现已经没时间了。

赛时期望得分：100+0+8+0=108。

赛后

赛后马上就是军训。和同学吐槽完题目难度后讨论了一下，发现 T1 似乎没判前缀和 s_i\le m，可能要挂分，且是 (0,100) 间随机挂分，顿时感觉自己完了。在洛谷上自测了 90，云斗上测了 95，安慰自己 CCF 数据强度不大，最多挂个 10 分。

但周三的时候我妈帮我远程查分发现是 108，感觉又活过来了。猛然想起我的前缀和只算了一部分，超过 m 的可能性变小了。虽然有可能被卡，但比其他人更难卡一些，于是幸存，但其他做法似乎挂了 5 分。在这里，再次感谢 CCF 的数据提供者。

鉴于本次 NOI Plus 难度过高，感觉自己分数应该能过省二线（吧？）但又因为 T2 部分分竟一分没得，还有上升空间，下次仍需努力。

NOIP 考完后，我必须回归文化课了。我不可能拿牌，因此文化课是必须要面对的，但英语的一次次分数将我痛击得体无完肤。我不像 bcz，fwl，clw 等一干大佬一样文化课很强，起码有退路可走，感觉前方马上到来的月考又是一次劫难，愿我顺利渡过吧。

今年的赛季于我而言已然结束，但没时间感伤，我又要投身于紧张的高中学业之中。希望大家都能获得理想的成绩，至于我，只能明年再战了。

CSP-S1 2026 RP++！（bushi