NOIP 2025 游记

· · 生活·游记

前情提要：CSP-J 2022 首战告捷，CSP 2023 入门组最后艰难战胜 T4，提高组 150 惜败 ZJ 1= 线，CSP-S 2024 拿下 ZJ 1= 并压线抵达 CQ 1= 线，遂参加 NOIP 2024（游记没写），忘了在考场上干什么了，只记得赛时不会 NOIP 2024 的任何一题 其实现在也不会，遂暴力收场，仅抵达 2= 线。

CSP-S 2025，慢速通过 T1，T2 赛时认为自己过了结果距正解复杂度还多一个 \log，T3 在赛场上尝试字典树上 KMP 结果因为计算 next 指针的方法错误导致整个算法假掉，T4 只会朴素暴力甚至没有意识到 n=m 的 4 分非常好拿从而没有写，最后计算分数的时候百位算错从而游记未过审一次， 整体非常难以评价。不过最后还是力压 ZJ 1= 线并取得体验 NOIP 的资格。

打了若干场模拟赛，难度尚可，但是最后一场模拟赛不会 T1、T2 中的任何一题，遂暴力收场，打完发现 T1 绿 T2 蓝，遂题字“败于绿矣”。

发现自己连绿题都不会做，如此成绩，如何 NOIP？

给正赛攒 rp 攒满了。

赛前之夜

乘车往杭州，入住一酒店。

路上自然还是杭城夜景，还有那钱江，甚至路线都与 CSP-S 2025 去程基本无异。倒是车子被门口的升降杆创了两下，引众人大笑。

酒店门口的广告有点难以评价，正好车子转弯放慢速度，遂引众人前来拍照。

事实是从赛前一天下午开始就没几个人认真在学了，有塞勒斯特者，有弗洛尔艾欧者，我简单地默写了 SPFA、KMP（好像正赛前用伪代码默写 KMP 已经成为我的惯例了）板子，然后在一张餐巾纸上用铅笔默写了树剖，后面也什么都不想干了。到了车上又有几个菲格罗斯者，不过我的水平过于菜连这种东西都不会打，遂随机看了一会儿塞勒斯特、菲格罗斯和杭城夜景。杭城为什么这个时候就开始晚高峰了，经过两个小时（好像比地铁只快了半个小时不到），方抵酒店大堂。

经过半个小时的等待后拿到房卡，成功入住酒店九楼一房间。后欲串门，结果我的房卡放在了房间里用于插卡取电，同住的 yyy 的房卡放在了他的衣服里然后衣服被他放在了房间里面，出房间照例需要关上房门，然后我们就被成功地锁在房间外面。遂往大堂补办一张房卡。

后面就是随机串门。tcy 不和我们同一酒店，而 yqf 的房间位于同酒店十楼，去十楼串访未寻得，倒是他后来下来来我们的房间串了一会儿。发现现在这个点基本上也没几个人在正常复习了。

我也忘了那晚究竟还干什么了，倒是只记得十楼有一神仙，塞勒斯特而不闭户，不可不谓勇矣哉。遂闭其户。

九点半才睡，本来以为这个点很迟，结果十点左右有二神仙按我和 yyy 房间的门铃，yyy 开了门，没想到这个点都还有串门的啊。他们是不是把 Codeforces 给光速 AK 了，闲的没事做。

次日早上六点二十左右便起床，发现房间里有个“请勿打扰”的开关，遂将其按开。

然后出门随机游走，回来的时候发现房卡还锁在房间里，幸好 yyy 在里面，但发现此时按门铃根本无效因为我刚才在里面打开了“请勿打扰”的开关，遂敲门，最后 yyy 开门让我进去了。

整理完东西后下楼吃早饭，吃完早饭去大堂集中，人都到齐之后出发前往杭师大（还是那个地方考试），由于队伍过长，三次红灯亮时还有一半队伍在斑马线上，一次创飞一辆电瓶车（当然最后把它扶起来了）。

由于集训期间在机房，与其他同学基本上是物理隔离，自然无需担心被流感传染的问题。yyy 和 yqf 同一考场，因为只有我是难以评价的 Windows 选手，不过据说 yyy 看到了 byc、dly 和戴着退烧贴（完了我写这句话的时候头开始发热怎么办）的 sxy。

以及，进场的时候，一同学忘带准考证，他在门口停了一会儿，最后还是进来了，有人评价他的 rp 应该是全场最高了 因为他把准考证都献祭了。

赛中之时

解压完压缩包密码，开始看题。

看上去这四个题都很不一眼，想了一会儿发现 T1 只会先选一些糖果购买一个，然后选 x+y 最小的糖果购买尽可能多的偶数个。

然后发现第一步选的若干个购买一个的糖果，一定是 x 最小的那几个，遂解出 T1，不到开考半个小时便通过了所有大样例。

恐怕出题人是怕我们爆零难看吧。

后面钦定商店卖的糖果为棒棒糖。

尝试解 T2，发现那个买棒棒糖的人误以为棒棒糖可以无限分割（其实不需要无限分割，只需要两块钱的棒棒糖可以被分割成两个现价为一块钱，原价为原来棒棒糖的二分之一的棒棒糖就行），发现这会出错的唯一情况是遇到一个两块钱的棒棒糖（原价为 y），但手上只剩一块钱，只能从后面挑一个原价最大的一块钱的棒棒糖（原价为 z）或者后面没有这样的棒棒糖（这时钦定 z=0）。但是我们之前买过一些一块钱的棒棒糖，设原价最低的那个原价为 x，而把 x 和 z 扔了换成 y 更优，即 y>x+z，这个时候他那个策略就不对了。

遂考虑把所有 2n 种可能的棒棒糖全部排序，枚举 y 和 x，因为 y>x+z 故 z<y-x，然后取到 y 之前棒棒糖价格正好 m-1，可以用背包维护；后面部分，因为没有价格限制，已知 z 上限，方案数是唯一确定的，而这可以用后缀和预处理出来，查询的时候也可以用二分查找等方式，方便我们的计算。

大力分讨可以得到一个 O(n^3) 的做法，但是继续优化均失败。甚至一度以为自己得到了 O(n^2) 的做法，结果分析完发现还是 O(n^3)。

此时脑子已经很糊，贸然写 O(n^3) 估计大概率也会挂，遂暂时性放弃，转而打 T4 暴力。

T4 想了一想，得到了一个先把所有询问的区间长度离线下来，然后求一遍前缀和把区间和转化成两个前缀和之差，枚举每一个待询问的区间长度，再枚举每一个这个长度的区间，计算出区间和，然后把这个和放在区间左端点处，然后包含一个特定点 i 的所有该长度的区间经过上述处理之后刚好落在一段区间内，直接 ST 表维护，查询的时候再暴力计算答案的做法，其实我场上可能也不知道这个东西能拿多少分，不过应该可以至少过第一档暴力。光速写完并测完，并没有出现答案错误，不过由于杭师大的机子 1 秒只能做 10^8 次左右的加法运算，因此完全无法确定我这个东西能够拿几分。

发现 T3 只会 O(n^n) 的暴力，转而继续想 T2。

差不多十二点钟发现，大力分讨完之后，背包维护的是这样一个问题：有 a 种棒棒糖，每种花费为 1 元或 2 元（不妨称之为 A 类棒棒糖）；另外还有 b 种棒棒糖，每种花费 1 元或 0 元（不妨称之为 B 类棒棒糖），求总价恰好为 c 元的方案数。枚举 y 再枚举 x，a 和 b 的值可以一边扫一边算，c 也是容易计算的。然后钦定所有 A 类棒棒糖定价 1 元，B 类棒棒糖定价 0 元，剩下还有 c-a 元未分配，而总共有 a+b 种棒棒糖可供分配，每种棒棒糖至多再分配 1 元，总方案数显然是 C_{a+b}^{c-a}；再计算出符合题意的 z 上限值，查出后面部分对应的方案数，两者相乘即是这组 x,y 对应的不合法方案数，再加起来得到不合法方案的总数，用总方案数一减得到答案。

分析了一下，复杂度应该是对的，正确性也没假，遂开写。

此时已经十二点多，其实还是有点慌的。十二点半左右写完，一测，无法通过样例。仔细检查，发现自己犯了一个难以评价的错误，改完，再测，过小样例了。

开始测大样例。强制深呼吸让自己冷静下来。

找不到差异……找不到差异……找不到差异……

前十个样例过了，最后一个样例能过吗？

怎么还没跑完啊？

原来我的做法在 O(n^2) 的基础上多了个二分查找，实际复杂度应该是 O(n^2\times \log n)……但也……不应该这么慢吧……

终于跑完了，一比较，答案没错。

我，应该是做到了吧。

看一看数据范围，这个复杂度，最后两个测试点有点悬，不过也就 8 分。现在已经是十二点四十，T3 的 O(n^n) 暴力也有 8 分，并且更加不容易写错（T2 优化假了那是连 O(n^2\times \log n) 的 92 分都没了），遂开始写 T3 暴力。

T3 暴力写完是五十五分前后，似乎代码都是按照试题英文名称字典序升序写完的。

用最后的五分钟填完代码字节数确认表，感觉 ZJ 不填 MD5 确实有点难以评价了。

十三点，出场。我知道，我做到了。

赛后之归程

怎么全不会 T2？T2 赛时的体感难度，最多只有上位蓝吧。

有段时间洛谷评级是黄黑黑黑，我怎么可能场会黑？还好后来改成黄紫黑黑了。

简单交流了下 T2 做法，然后就被 yyy 批成场上发明范德蒙德卷积（事实上我当时可能不知道范德蒙德卷积是什么东西，后来查阅资料可得，NOIP 一个星期前的 AtCoder Beginner Contest 433 F 题可以用范德蒙德卷积做，然后我未能场切，但 tcy 和一同学场切了，所以他们才是真正的范德蒙德卷积的发明者）……

没想到，就在一个星期前，范德蒙德卷积考过，那就真有点难以评价了。

回去的车上一同学在打 gal，路线也和来时不一样（似乎是没走过的）。

比赛日之后

vp CodeForces Div.2，T4 不会，诚败于绿矣。

随机跳题跳到洛谷 P9196，怎么和 CSP-S T3 这么像？难以评价。

出分时间由六号提前到三号，由下午提前到中午，最后 100+92+8+40=240 收场。

感觉 CSP-S 和 NOIP 模拟赛的 rp 全加到 NOIP 正赛上了。

T2 挂的 8 分符合预期，不过 T4 我的代码能拿 40 分实属意料之外。这下 CSP-S 成绩严格低于 NOIP 2 分。

如此成绩，如何如此？

以及 ZJ 为什么不给初中体验类选手的代码？难以评价。

不过 tcy 直接发帖询问了，目前并没有看到有效的解决方法。

看来把 NOIP 出成这种难度，还是太难以评价了。

莫名地怀念过去的 NOIPlus 模拟赛。这才是真模拟啊。