NOIP2025 游记

jiazhichen844 · 2025-11-29 20:35:17 · 生活·游记

省流：只过两道，爆炸了。

在 O(1) 天前被流感击杀了，所以模拟赛打的很寄。

感觉正赛要爆炸了。

8:30 开始，密码 !noip@Nov29,2025:dream。

准备前 30 min 不动键盘，先口胡 300。

看一眼题发现 T1 应该不难，T2 counting，T3 不是 counting，T4 是 O(nq) 的 ds。

8:40 发现会了 T1。去想 T2。

8:50 发现劣的情况只有买的两个 w=1 比没买的 w=2 劣，直接在 a 排序后枚举这三个位置然后再随便做做就是 O(n^4)。

8:55 发现这个可以范德蒙德卷积后就是 O(n^3)，并且其实只跟两个比较有关系，先去想 T3。

9:05 不会 T3，破防了，写好遗言了，先写。

9:11 通过 T1 大样例。

9:30 通过 T2 大样例。

10:07 想了一年 T3 只会 O(n^3) 并且难写爆了，去看 T4。

10:20 发现 T4 有一百万种做法做到 O(qn\log n)，分治单调队列可以过 1\sim 4,13\sim 15，35 分。

10:40 中间认为自己会了 T4 O(n\sqrt n\log n+qn)，准备写发现假了。

11:20 把 T4 分治敲了，调了一年，感觉要爆炸了，寻找跳楼点，此时应该 100+100+0+35=235，去想 T3。

11:50 突然发现 T3 有一种状态是设 f_{i,j,k} 为 i 子树 j\times\text{mex}+k\times\text{空点数量} 的 \max，感觉是可以推的。

12:10 推出来了，复杂度是 O(nm^2)，感觉是好写的。

12:20 大样例过了，中间唯一一个挂是没写 m++，此时应该是 100+100+76+35=311，勉强比较 win。

12:25 尝试把 T3 一维干掉，感觉不会，去拼 T4。

12:40 发现 A 性质是好做的，直接单调队列，通过大样例。

12:50 发现 B 性质也是好做的，随便预处理，通过大样例，此时 100+100+76+60=336。

12:55 重新测了四题大样例并检查+填表。

并没有打块。

出场发现 zzzcr 和 xieruyu 批话声称不会 T2，ricefruit 100+100+76+50=326，thomaswmy 把 T3 秒了。

发表了一些批话，成功在 LA 被禁言了。

希望不要挂分。

upd on 2025.12.3：

哈哈，挂了两个题，哈哈，批话说多了，哈哈，这下真要 more more jump 了。