NOIP 2025 游记

· · 生活·游记

初一体验生。

day -9

确诊甲流，停课一周。

day -7 ~ -1

在家做随机题目，每天大概 4 ~ 5 题，连道稍微不那么板子的蓝都做不出来了。

day 1
7:50

到达考场。

8:25

进入机房。居然是沙坪坝校区初三的老年机房，不要！！！
还好，电脑环境已经重新配置过了，而且还换成了 g++ 9.3.0。遂打缺省源。
监考员居然是 gm，真是令人感动。
我的位置居然是 cyb 巨佬 之前集训时坐的位置，这更令我感动了。

8:30

解压，答题。
通看一遍题面，T1 像是贪心，T2 像是 dp，T3 不知道，T4 像是神秘 DS。
开 T1。发现可以 dp 拿 45 pts，而后发现至多有一种糖的出现次数 >1 ，优化为 01 背包。
什么，01 背包的价值居然全是 1？！
那不管了，直接排序、贪心，20 min 切了。

T2 没什么思路，直接暴力 20 pts，此时大约 10：00。
开T3，发现可以状压 dp + 子集枚举骗一点分，遂开写。
……
……
发现做法假了，遂改成了 O(N \times 4^N) 的诡异算法。
什么，大样例 2 居然只跑了 0.6 s?
T4，初步思路是对于每个 a_i 维护每个长度的最大和，再用 ST 表维护，然后发现会 MLE。
发现可以用单调队列维护最大区间，遂改成了 O(nq(R-L)) 的做法。
然后发现对于 B 性质，可以预处理再做，而后加上去了 。
大样例 2、4 跑了 1.2s，3 跑了 0.8 s。
40 pts。

11:30

打完所有题目的代码，开始检查。
T1 一边对拍一边看代码，发现自己没判

if(sum>m){
  break;
}

加上，接着对拍无误。
T2 本身已经足够暴力了，不可能对拍。
T3 对拍，验证正确。 T4 没有对拍，但肉眼看出来把

min(32,n);

写成了

32

测小样例，RE 了。而后改正无误。

12:30

生无可恋，等待考试结束。

后记

估分：100+20+16+40=176 pts。

终章

没有挂分。 T4 连个回滚莫队都想不出来，我还是太菜了。