NOIP 2025 游记

· · 生活·游记

前言

CSP-S T2、T3 被卡常，2h 没做出 T4，排名低于去年 CSP-S、NOIP。

好在这次是 CSP，我还有时间。

最后的不到一个月，成败在此一举。

:::align{right} —— CSP-S 2025 游记 :::

11.7 \sim 11.28

NOIP 2025 前训练记录，可能会在未来的某一时刻公开。

11.29

NOIP 2025 RP++！

差不多 8:20 到了考场，简单打了个 36 行板子，然后时间到了开始看题。

T1 是容易的，5 分钟秒了，一遍过样例，8:40 交了上去。

T2 一眼看上去非常困难，一开始一直在想 dp，后来发现 dp 没有办法钦定一个东西的价格到底是 1 还是 2，所以做不了。上了个厕所决定先看 T3，这个时候大概 9:00。

看了几分钟 T3 没啥思路，又回来做 T2，忽然发现只要枚举两个位置组合数随便算就行了。花了不到十分钟写完了，修了一下小样例过了，第二个样例过不去，很急。

冷静下来发现有一个答案是 31 我输出 32，对着调发现有很大问题，于是加了个双指针改了改系数输出对了。但是还是有一部分输出比答案大，仔细观察一下代码，发现一开始写的 break 没删，然后就过了所有大样例。

这个时候大概 9:40，我发现最后一个大样例跑了将近 0.3s，就卡了卡常，结果一不小心还改错了……后来发现要判 \le n，改了之后 0.09s 过了。然后不知道按到了什么键，虚拟机窗口缩小了，监考老师来了也不会弄就直接退出重进了。不过还好代码保存了，9:50 交了上去。

继续思考 T3，又想了二十分钟仍然只会指数级暴力，于是先看 T4。T4 看上去是传统数据结构，但数据范围比较抽象。简单思考后会了 A、B、D 性质，但没有取得进一步进展。

上了个厕所，感觉可以类似单调队列维护，每个右端点对应的只有一个左端点是有用的。然后类似滑动窗口，每次删不合法区间，将一些区间的左端点改为 i。进一步思考后发现这一定是个后缀，所以只需要维护三个双端队列（第一个“过期”，第二个正常，第三个左端点相同）就做完了？

这个时候大概 10:40，写了 10min 发现不太对，左端点相同的连续段不一定只在最后出现，思考了一会儿发现用链表维护连续段就行了，然后在 11:00 左右开写。

写了 40min 差不多写完了，然后小样例就调了 20min，调出了包括链表合并在内的一堆 bug。没想到第二个样例输出完全不对，着急。

感觉没时间造小数据了，就写了个暴力对比哪次询问输出错了。输出了一堆调试信息，调出了一个大于号和大于等于号的 bug。然后莫名其妙地发现双端队列的队首对应的链表是空的，于是输出了整个双端队列，发现我双端队列里有一堆编号一样的链表，导致取出链表的时候可能已经被清空了。观察了一下发现有一个地方不该 push_back，改了之后通过了所有大样例，最慢的 1.3s。

这个时候大概 12:30，感觉也没时间卡常了，所以就直接相信 CCF 评测机了。赶紧回去冲 T3，感觉肯定要 dp 但还是没有想出 O(\text{poly}(n)) 的做法，只能开始拼部分分。

花了将近 10min 写对了 m\le2，然后写了个 O(2^nn)，发现板子里忘记 #define pb push_back 了，当然我不是强迫症不会弱智一样改四个题的代码的。然后开始调，调出一堆 bug，还是过不去样例，最后一分钟试图改成 O(4^nn) 然后失败了。

估分 100+100+8+100=308，问了一圈发现可能上不了队线/ll

那还能咋办呢，只能希望不挂分吧。

赛后发现 T3 我写的暴力好像假了。。。但是有个十分钟就能写完的 O(n^3) dp，为啥我没想出来？？？延迟钦定 dp 状态设计我的一生之敌。

下午写了个 T4 题解，发现我的做法和全世界都不一样，不会经典套路导致的。。。但是我的做法其实很好写，只不过一堆调试内容导致赛时代码长达 5k。

晚上看了看游记，发现 BJ 甚至有个 CSP-S 两百出头的 NOIP 估分 316，这还是人吗？？？

加训 dp！！！

12.3

出分了，100+100+8+100=308 没挂，应该是苟上队线了。