NOIP2025 游记

· · 生活·游记

考前停课两周，因为连续两场比赛（NOIP2024&CSP-S2025）爆炸，导致心态很不好。

在洛谷上只要起得来的 NOIP 模拟赛都能写出来 T3，自我感觉良好。

在学校里的模拟赛有一半能写出来 T3，于是定下目标：冲击 300+。

赛前一直担心 T1T2 很难，因为我的所有能接受的策略都是基于切 T1T2 的。

赛前两天教练找我们分享了策略，会了文本比较省略空行空格。

Day 0

很紧张，一直做梦明天做 T3 的场景，觉得 T3 要考数组，有可能交互。

Day 1

被分到了 bsd 考点，似乎所有 S 考炸的都来这个考点了。

那里不让提前写代码，于是等待，这之前练了道绿作为热身，感觉绿做的都没那么通畅，很害怕。

开始了，开 T1，一眼没思路，但是想一下发现可以 x_i+y_i 合并，然后变成若干价值 2 的无限物品和 n 个价值 1 的物品。

然后随便枚举，又花了 1 min 试图挖掘更多性质，找不到就不管了，大样例过了，使用约 10 分钟。

期望得分 100，预期难度黄。

开 T2，一眼出大体思路，在草稿纸上画了几下，然后觉得能写了。

开写，然后没过样例，用种情况忘讨论了，不过还是能想。

加了双指针预处理等东西以后，还是不过去第一个大样例，发现第三组样例 m=2，开始条那个，手玩的时候发现样例有很多性质，看上去是手造的。

于是小样例和那个样例轮番轰炸下代码在切完 T1 后 1.5h 调过了，发现减法完没加模数，过了全部样例，光速检查后改了。

期望得分 100，预期难度蓝。

然后开 T3T4，预约了上厕所后把题看了，切完 T1T2 就是喜欢上厕所庆祝。

T3 第一眼不会，然后看部分分数据范围，发现有 n\le360，于是考虑 DP，发现容易的。

本来到这里我应该写完开 T4，但是我觉得我没用上 m 挺憋屈的。

于是继续考虑，深挖 DP，发现可以钦定重儿子，然后每个点贡献就是到根最长连续重边长度加一，于是就是 O(nm^2)，写了个 vector 就跑了，花了一个小时。

期望得分：76，预期难度：紫/黑。

开 T4，一眼看过去没思路，但是研究部分分发现可以很简单的单调栈拿 40，发现困难点的单调栈可以做到 O(nq\log n)，瓶颈在于静态和 k 取 \max，但是感觉细节很多，而且和暴力一个分，就不管了，写了 40 跑了，花了 75 分钟。

预期得分 40，预期难度 紫/黑。

然后还剩半个小时，我决定检查一遍，检查时差点以为 T1 挂了。

其实试图写 T4 单 log，这样就是 50，但是觉得纯浪费时间，就没写了。

估分 316。

出来之后非常兴奋，因为我上两次比赛都是 200 出头甚至整，不过出乎意料的，我以为大家都 300 多，因为我确实觉得这几个分比较简单，都没咋思考，不过似乎都 T2 没调出来，我很意外。

有一半概率有队线。

回家，T1 自测能过。

T3 发现 vector 开 360^3 会炸，于是 -8。

T2 能过（云斗），洛谷卡成了 92。

T4 没测，但是 40 不至于挂。

综上，估分 308。

别额外挂分。

另外，赛后交流发现 T4 那个思路是对的，因为单调栈求出来的区间性质，静态区间 max 可以把所有区间延长一定长度，使得不包含，然后就能单调栈计算了，复杂度线性，感觉天塌了，差点每个题都拿到大分了。

综上，T4 是紫。

预估难度：黄蓝黑紫，和去年差不多。