NOIP 2025 游记

· · 生活·游记

NOIP 2025，就像梦一样。

!noip@Nov29,2025:dream

CSP-S 2025 游记

快进到考试日。

2025-11-29

前一天晚上总之还是有一点紧张的，快到十二点才睡。早上六点半就醒了，但挣扎了许久，七点才起。
晚睡早起，很坏了！
依旧决定短袖加外套加一层裤子，等到了考场把拉链拉开披着就好了，毕竟考场真的很热。
带了某提神功能性饮料。
路上用手机最后看了几遍扩展欧几里得和线性预处理逆元。

八点二十几分艰难到达考点。路上怎么这么滑 QAQ。本来想着跑快点不会太冷的，但跑了几步感觉不对后决定还是不跑了。
然后就在走的时候滑倒了 QAQ！布嚎！
进到楼里已经基本只能看到围在线外的家长了，迅速钻进隔离线跑到考场门口，在考场外放好外套后光速钻进考场。
拿到签到表签到，迅速寻找到自己的位置然后钻入。不小心撞到后排的挡板了 QAQ，很坏了。
看了下时间，八点二十八。迅速重启电脑更换 Linux 系统。摸了半天摸不到重启键，于是低头寻找。起身的时候不小心撞到旁边同学胳膊了，然后两个人互相疯狂向对方道歉。
似乎是上次 CSP 有个考场的代码没收到晚交了，这次使用的是新的代码收取系统。其实前几天就收到了新系统的使用教学。直接下载试题就好了，不用等监考老师拷贝，也不用使用那神秘的 ftp 登录 INF 遍登不上去。
感觉准考证号加身份证号后六位作为密码登录感觉还是很坏了，知道别人准考证号和身份证号显然就可以替考或者故意在别人账户上提交爆零代码，或者查看别人已提交的代码抄袭。不过查日志查内网 IP 显然可以复原攻击。希望不要有人这样做吧。
拿到题面大概八点三十二，在草稿纸上光速写下扩展欧几里得和线性预处理逆元的关键式子后决定先看题。
（是真的很怕忘了 QAQ）

大约十一分钟时想到了 T1 的一个贪心结论，不存在两种糖果都选两颗及以上的可能。在草稿纸上简单画了一下证明，感觉应该是对的。
于是有了一个很贪心的做法，将所有糖果的 x_{i} 都放入一个优先队列，每次取队头，同时记录糖果编号以及选的是 x 还是 y，再放入它对应另一颗糖果。对于 m 比较大的情况，记录第一个被取出的 y_{i}，然后疯狂的选这一组 x_{i} + y_{i}，最后再将剩余的钱用原先的优先队列填至一颗糖也买不了。
感觉是一个很对的贪心，于是决定去看后面的题。

大约三十八分钟时读完了所有的题目，做了一个简单的预估，T1 m log n 的优先队列可以得到 65 分，拼上特殊性质 A 可以到 70 分，加上贪心后可以获得 100 分；T2 似乎只会 2^n \cdot n 的 20 分，感觉 m = 2 似乎可做，应该还会有 20 分；T3 只会 n^n 做法，预期 8 分；T4 很数据结构，但只会到 qn(R-L+1) \log n，似乎可以过特殊性质 A 和 B，预期 5 到 30 分。
此时总预期 100 + \left[20, 40\right] + 8 + \left[5, 30\right] = \left[133, 178\right]，决定开始实现 T1。

大约五十分钟时实现完 T1，但是测样例一就很不对。看了一下样例发现之前的优先队列策略很显然是错的，样例一很好的查出了这一错误。很显然第一种 x_{1}=4,y_{1}=1 要比 x_{2}=3,y_{2}=3 总合更少，但如果每次都选最小值，显然永远都只会取总合更劣的第二组。
我开始慌了。
我想起 NOIP2024，同样是 T1，同样是贪心。那依旧是我至今挥之不去的阴影。
或许有些人说 T1 恐惧症只是玩笑吧...但对我来说，是真创伤，真应激，真 ptsd。
OI 啊... 你到底带给了我什么... 你还要从我这里夺走什么...
我曾无数次梦见我身处 NOIP 的考场上，面对着久久做不出的题目，然后惊醒。
我多么希望这只是一场梦，醒来时可以发现，自己依旧躺在暑假时的那张床上，看着周围的几位室友。
为什么...为什么我还没有惊醒...
原来...这是真的 NOIP 吗？
!noip@Nov29,2025:dream
我该在哪里跳楼？我问我自己...

考场不是用来写回忆录的，你应当珍惜你通过漫长的训练换来的参加比赛的机会。

我强忍着不适，又想了许久。我又想了数种贪心的想法，然后又手造样例否定了这些思路。
我彻底慌了。
我试图让自己镇静，但身体的不适愈发强烈。我难以集中精神。
我呆呆地望着数据范围那一页。
我注意到 n \le 10^3 , m \le 10^4 的部分分有 65，再加上特殊性质 A 有 70。
我想到背包！！！
我瞬间精神起来，我想到或许我之前的思路完全偏了，或许这是一道优化 dp 的题。
我们可以把每一种糖视作两种物品，其中重量为 x_{i} + y_{i}，价值为 2 的有无穷个，重量为 x_{i} 价值为 1 的有一个。
于是我光速去实现了这个算法，顺利通过了前六个测试点和全部手造样例。
虽然是 OI 赛制并不能得知分数，但我还是交了一下代码防止意外。
之后我开始想优化，但很显然我想不出。想了一会后想到 x_{i} + y_{i} 最小的这一组最少会买到剩余的钱小于等于 \sum x_{i}，又想了一下显然同时满足最多比全选至钱不能再选的情况少选 \lfloor \frac{n}{2} \rfloor 组。虽然即使只背包这最后的一部分空间也是完全不可行的，但很快我想到了一个新的贪心。我们可以按 x_{i} 排序，再计算前缀和；从大到小枚举 x_{i} + y_{i} 最小的这一组要卖多少组，然后二分剩余的钱可以买多少个单独的糖果。我们显然可以及其简单的把结论推至 x_{i} + y_{i} 最小的这一组最多买 \lfloor \frac{m}{x_{i} + y_{i}} \rfloor 组，最少买 \max(\lfloor \frac{m}{x_{i} + y_{i}} \rfloor - n, 0) 组。
于是此时时间复杂度来到 n \log n。
光速实现后通过了全部大样例和手造样例。测完样例后我又提交了代码。
此时时间已经过了大约一百一十分钟。但我很快意识到如此简单的思路或许身边的很多人早已通过此题。

你不应该思考其他人，包括你所认识或熟悉的选手的发挥，不要揣摩 XXX 能不能过这个题，不要揣摩做不出这道题目该怎么办。

我决定倒序实现。
T4 延续之前的思路，枚举起点，枚举长度，统计这一段的和（前缀和优化），对这个区间刷最大值（仙丹树优化）。于是我开始实现仙丹树。调了好久终于调过，糖丸！仙丹树都要写这么久！
之后我开始实现具体的逻辑，然后发现仙丹树还是有问题，无法处理负值 QAQ。光速修改完后顺利通过第一个样例。测试完大样例后复制了之前的比对程序比对答案，发现全错了 QAQ？发现是比对程序的读入是 int 类型，于是光速改为 unsigned long long 类型重新比对，结果还是错一堆 QAQ？继续排查后发现是仙丹树每次询问重置最小值的逻辑有问题 QAQ！修改后终于通过大样例。不过样例二要跑 3 秒，样例五更是要跑 30 秒 QAQ！
布嚎！
只能期望评测机跑快点了。不过本身本地机器就要比评测机慢一些。希望能水过第二和第三个点 QAQ！

又看了下 T3 的暑假范围，在草稿纸上画了下感觉 m = 2 时似乎叶节点全部填 0 根节点填 1 就是最优的，然后看了一下样例发现不对，又去看了下题面发现根节点的深度为 0。
于是光速实现了 n^n 的 dfs 做法。

于是去写 T2 的 2^n \cdot n 做法。写完后去细想 m = 2 的做法，想了一会发现并不会。然后去想了特殊性质 A 和 m = n - 1，认为答案是 2^n。发现并没有大样例有这两个特殊性质的，于是手搓样例验证了一下发现似乎是对的。不过也确实，如果给大样例那就太好猜测和验证了。
剩余最后半小时写完，想了一会特殊性质 B，感觉很有前途的容斥，但是想了一会不会做。

最后十几分钟开始检查提交，查看有没有没注释的调试信息，输入输出文件名，常量。
监考老师一直在前面说话，而恰好又坐在第一排面对老师的我又承受了这一巨大的噪音 QAQ。最后一直在提醒抓紧提交，截止后久不让再提交了。而有些同学直到最后也没有提交任何文件。监考老师：“你提交个输出 0 的 cpp 也行啊！什么都不提交？”
最后在草稿纸上超了 MD5 值和文件大小，然后一个一个去前面核对 MD5 值。

出场后我忽然意识到我的 T1 判断用 dp 还是贪心的写法有问题，我似乎将常量 maxm 设为了 1.1 \cdot 10^5。这也就意味着只要 m \le 1.1 \cdot 10^5，都会执行 dp 的代码，而最后几个点的 n 也可能到 10^5。

我感到一阵眩晕。

!noip@Nov29,2025:dream
多希望这只是一场梦...
可取反的优先级不高
NOIP 2025，不是梦...

我该在哪里跳楼？我问我自己。

考场出来的路依旧很滑，我狠狠的摔在了室外长长的楼梯上。

我不知道今年的 T1 又会送走多少人，也不知道自己会不会是其中的一个。
真创伤，真应激，真 ptsd。

预期 \left[65, 100\right] + \left[20, 28\right] + 8 + \left[5, 30\right] = \left[98, 166\right]。

2025-12-03

查分，100 + 24 + 8 + 5 = 137。

拿到数据和解压密码，我开始批量测试。但 NOI Linux 2.0 自带的批量评测软件似乎 bug 过多，不仅经常闪退，分数还会错。有时刚评测完分数是对的，评测下一给人时就错了。我也不知道 T1 20 个点等分，一个点 5 分，它怎么给评测出一个个位数是 4 的分数的。
严肃决定自己重写一个评测程序！

下午在某批量测试网站上看到了成绩，rk 5。不过前面的两个准考证号感觉很怪。其实在拿到公示文件的时候就注意到了，因为我省一共就没有这么多名额，而初中名额虽然在我旁边有初中的有正式准考证号，但提交的时候明明看见有很多准考证号是 TYS 开头的。

或许那四个半小时的坚持与挣扎，带给了我在 APIO 跳楼的机会。

或许能进省队呢？我想。
那就等 NOI 再跳。
我就是靠着这样一次又一次的不甘与对未来的希望活到现在。

我常常追忆过去。

我该在哪里停留？

OI 啊... 它带给了我生的希望。

我爱OI，我恨OI。

我从人间走过。