NOIP2025 游记

· · 生活·游记

Day 0

我要摆烂。尝试在教练眼皮子底下刷知乎未遂，被眼神警告了呜呜。

晚上入住宾馆，吃下一片褪黑素，在昏昏沉沉的风声中缓缓睡去。一夜无梦。

Day 1

开题。T1 是简单的，2min 写掉了。

看 T2，一开始看成了全局最优，被硬控 10min 后决定先模一下样例，然后发现自己想假了，可恶。于是决定重新思考，从确定 w 开始，最优的决策一定是先像小 X 一样贪心再反悔一下，刻画一下形式后感觉能勾勒出一个大概的轮廓，用数学语言写了些条件好像就会了。此时已经过去了整整 1h，按照往年节奏已经非常不好了，着急，去厕所洗一把脸冷静下来后先打了暴力验证正确性，又花了 1mol 时间才写出正解，一抬头已经 9:00。

看 T3。已经确定了每个点的值的子问题好像是做过的，直接记录 mex_u 然后从下往上递推即可。突然发现这个东西很能用延迟钦定的方法 dp，可以变成 O(n^3)。但按往年的难度这题非切不可，于是硬 push 自己接着往下想。突然发现可以刻画一下每个 u 取最大的 v 在哪里，刚好是链剖分的形式，这样就是 O(nm^2) 的，但是过不了题啊！接着就被硬控了 0.5h，毫无进展。

很慌，感觉已经落后于队线了，赶紧去看 T4，但人在慌乱的状态下是什么都分析不出来的。想了半天发现有一个 O(nq\log n) 开几个线段树硬维护的做法，但拿不了什么分啊。

T4 也不是善茬，滚粗回去想 T3。一百万个假做法，最终确定自己就是不会这道题，崩溃。赶紧拼完了暴力接着 T4。此时 11:45。

时间不够了啊，无敌了。一挡挡暴力往上拼，为了卡常还写了几乎没怎么写过的 zkw 线段树，调了很久，哭哭。写完前 60 分就只剩下 20min 了，无所事事了一会儿突然发现了一个可以通过 DE 的分治做法。当时的我明显上头，在没进行过任何检查的情况下决定开冲。最后 5min，颤抖着写完了代码，发现根本过不去大样例！！！此时已经被巨大的紧张感冲昏了头脑，周围的考生一个个开始整理物品，我却选择继续调试，最后 2min 意识到不可能再调出来了，草草保存了代码，甚至还没来得及填写完字节表比赛就已结束。

四处打听了一下，才发现今年的题目真不简单。

应该是 100+100+76+60=336，但压根没检查代码，挂分概率巨大，怎么办啊 /ll

upd：100+100+76+55=331，T4 被卡常挂了 5 分。