NOIP 2025 —— 尽力就好

· · 生活·游记

前情紧要，S 估分 134 但假做法和暴力都过了比预期中更多的点，反向挂 36 -> 170。一等有了，NOIP 体验名额也有了。既然如此那我今年也就没有遗憾了，好好体验 NOIP 吧。

11.02 - 11.28：打模拟赛，补题，一切照常

这期间回学校考了期中考试，拿下初中以来最差名次。值得一提的是，社会考了 74 成功夺取 A 班倒一。不能再拖下去了。

11.28 考前一晚

睡不着，感觉很奇怪。明明这场联赛影响不了什么，或许是想为自己考差的 S 报仇吧。入睡，做噩梦。梦见自己不会 T1，梦见自己拿着两位数的分数狼狈回归文化课。梦醒。一切都还没开始，别紧张。

11.29 正赛

早上有点困。早饭在路上吃的，没啥胃口。好像没过多久就到地方了，收拾了一下就进了杭师大仓前校园。不得不说，早晨的郊区是真的冷qwq，但空气真的很清新。到了跟同学约定好的地点（考场门口的拱桥边上），发现 @lxh20110629 竟然比我到得还早诶，跟他瞎掰扯了一些闲话qwq（实话实说聊天确实很能缓解压力）随后 @yangzichen1203 大神也到了，善良的 yzc 给我们没人都分了一块士力架，心态 + 1。后来 @hxuwna，@yyc_qwq 也都陆续来了，打了打招呼就准备进考场了。

考场在 402C，进去发现是个好大好大的机房，看旁边的标语似乎这个机房还承办了 ZJCPC 2025。找到了自己的座位，老老实实地阅读考生须知（监考不让切换窗口，不嘻嘻）。08:25，报了密码，!noip@Nov29,2025:dream。解压完了之后看题。4 道传统，好的。T1 贪心，不妙啊。T2 计数，还行。T3 树形 dp，神秘。T4 ds，神秘。这么看来和去年构成很贴近啊。

08:29 开考，开 T1。联想到暑假的一道联考 T1，形式上基本一样但是那题我没补啊啊啊完蛋了。没事不急，现场再胡一个做法吧。最朴素的想法肯定是一直取最小的 a_i + b_i，其他的只考虑取 / 不取 a_i 即可（？）不管了看起来很假先写了再说吧。08:50 大概写完了，测了测样例，诶？？？怎么 #6 过不去捏 ...... 输出 82 答案 83。点开 candy6.in 一看 n = 1000, m = 10000 这我调啥啊！开始急了。我不会连 T1 都过不去吧，梦中的两位数分数不会要成为现实了吧。此时此刻曾在 28 天前上演：28 天前的 S T2 写了个只能过 #1 #2 的树上状压假做法调了一整场，如今我又对面前的假贪心苦思冥想。

我闭上眼睛强迫自己冷静下来，不能再重蹈 S 的覆辙了。果断跳 T1，开 T2，此时是 09:40。读完 T2 题面后毫无思路，我意识到这道题肯定不是 dp，而是一道性质题。开始手玩什么时候小 R 的贪心策略会劣，可惜毫无进展。看了看数据范围，O(T \times 2^nnm) 的暴力做法能过掉 #1~5 共 20 pts，果断开写，10:00 过了样例 #1 #2 #3，此时我感觉 T2 不是可做题，做出了最正确的选择：跳 T2。

看了眼 T3，只会 O(n ^ n)。诶算了先丢一边去吧，开 T4，ds 总是好拿部分分的。

T4 形式上和去年 T4 很像。读懂了题意之后会了 O(n \log n + qn^2) 的 st 表做法：枚举每个 i 可行的左端点 r，用 st 表记录前缀和最小值然后就能做了。花了 15 mins 实现了一下做法，发现过不去小样例。Debug eps-mins 过了样例 #1 #2，但 #3 要跑 5.25s，这 5 分应该是拿不到了。看了眼特殊性质 A，发现单调队列一下就做完了，10 mins 写完 + 5 mins 调试（求的是 \text{xor-sum} 写成了直接累加，糖丸了喵）。此时是 10:35 左右。

随后感觉 T3 也完全不可做，遂花 10 mins 直接写了个 O(n ^ n) 上去，一遍过了小样例，诶诶怎么只有一个样例啊，有点怕挂分。不管了先相信，当前得分 eps + 20 + 8 + 25 = 53 + eps。

目前的局势是，最显然暴力的已经打完，而时间也过去了 2h。那么现在的目标很明确了，把 T1 磕出来并在 T2 争取拿更多的分。静下心仔细想如何调试 T1 #6 n = 1000 的数据。看了看发现 #6 数据是随的，输出了一下 \min \{ a_i + b_i \} 发现只有 266，那么很显然很多组 a_i, b_i 都是没有用的，写了个程序只保留了 a_i + b_i = 266 和 2a_i \leq 266 的组，发现只有 15 组！！！这下显然好调试多了。手玩了一下算出来的答案也是 82，诶？？？怎么回事？？？但是可以证明答案一定能在这 15 组中拼出来，既然如此，写个爆搜看看怎么 83 的答案是怎么凑出来的。花了 10 mins 写完了爆搜剪枝后发现可以答案反悔了一个最大的 a_i！那么我的做法的错误之处就暴露出来了，改正也很简单，枚举反悔几个然后开个堆就可以做到 O(n \log n)，且正确性有保证。花了 10 mins 把改正版本实现完成，一遍过样例。此时内心顿时舒畅了许多，至少我有 153 分了，而在剩下的时间中我要做的只有尽可能拿更多 T2 的暴力分。

目光看向了 T2 的 A 性质和 m = 2n - 1 的 8 分，那么显然这两种情况下小 R 的贪心策略是正确的，答案即为 2^n。写完后看了眼 B 性质，毫无想法。发现只有 m = 2 的 20 分可以做一做了。我们在 a_i 降序排序后讨论一下第一位放啥，放 1 的方案数显然为 2 ^ {n - 1}，放 2 的情况似乎还得枚举一下第一个 1 的位置，然后分讨一下确定下一个 1 放在哪即可，而求下一个 1 的位置范围可以直接二分。这时候赶紧开写。

写完之后发现样例假飞了，有点急了因为此时离结束只剩下 50 mins。仔细想着自己的分类讨论和代码是否存在错误，果断先把二分改成暴力找，输出不变还是 WA。有思考了 10 mins 发现自己的讨论是有瑕疵的，改正后输出比答案少了 1。想了下发现漏了 w_i 全是 2 的情况，加上 1 之后发现样例 #4 有一处还是 WA。此时里结束仅有 20 分钟，想到快到手的 20 分肯能要离我而去顿时变得焦虑起来。我仔细扫着代码中的每一个细节却看不到丝毫破绽。我尝试注释了输出的那行代码，运行一下竟然发现还有输出！说明是我的数据点分治条件写错了！改了一下通过了 #4 的所有数据。我看向题面，发现样例 #7 也是 m = 2 的情况。果断运行，打开 cmd，输入完 fc sale.out sale7.ans 后闭上了眼睛，轻按回车。在那一瞬间我真的不敢睁开眼，我害怕控制台输出一处处与答案不同的行，我害怕这 20 分离我而去，我害怕就是这仅有的 20 分使我与省一和省选的体验名额失之交臂。

我缓缓睁开眼，控制台输出只有一行 FC: 找不到差异。在这一瞬间，难以言表的感受涌向脑海，此时离结束仅有 7 分钟。我知道，我尽力了，尽管分数看起来普通，但我发挥出了我的最好水平。既然如此，还有什么遗憾呢？

预估得分 100 + 48 + 8 + 25 = 181，希望别挂。求求你让我碰下省选吧。

Upd 官方成绩 100 + 48 + 8 + 40 = 196，终于证明了自己一回。

后记

之后就回归文化课了，从 09.03 一直脱产到现在我的文化课成绩已经烂完了。现在赶紧回去好好补补，但愿能努力考上杭二本部。加油吧，文化课总是比 OI 容易进步的。

说一些闲话，今年联赛的难度是我未曾设想的。其实高一这一届的同学们是最可怜的，第一次上战场就遇到天荒开局。。。希望大家都能在省选中翻盘进队吧，加油。