NOIP2025游记
SnowTrace
·
·
生活·游记
前情提要：
这段被删了。
Day -inf
完全意识到 NOIP 是手速比赛，开始研究总结模拟赛。
Day 1
进场，打了一个 NTT。
发现不是一个人一个桌，不过还是很宽敞，南航好评。
看了 T1 以后稍微想了一下，十分钟以内通过了
看 T2，感觉很麻烦，但是我猜 T2 一定是简单题，直接尝试枚举，编了一会。
$9:20$ T2 过了。
看 T3，一秒会了三次方，由于题目要求我复杂度和深度相关就开始现编，花了若干分钟对上了脑电波，然后想到了 dp 状态，看了一下 $O(nm^2)$ 看上去难以优化，决定先写完 76 再决策接下来干什么。
$10:10$ 写完了 T3 $76$。
看 T4，这题目怎么这么神秘，是不是又来了个 recall？
$10:20$ 不会做。
$10:30$ 为什么这个题这么多暴力分？
$10:40$ 发现 T3 状态中 $k-j>d_u$ 时 $j$ 没用，所以可以长剖，但是才 24 分太难写了先扔了。
$10:50$ 是不是分治一下就 $nq\log$ 了
$11:00$ 发现本质是倍增分块，那我可以把区间离散化一下拆成若干小区间，这样区间不交了以后跨过块的次数是 $O(\log n)$ 的，因此只需要查 $O(q+\log n)$ 次，开始写。
$11:30$ 快写完了，发现我后半部分怎么需要解决 $qn$ 次序列长度为 $q$ 的区间 rmq？倒闭了。
$11:40$ 发现原来这个结构可以预处理整块，但是常数很大。
$11:50$ 开始调。
$12:00$ 小样例过了。
$12:05$ 中样例过不去。
$12:10$ 发现边界情况有错，我是不是假了？？
$12:15$ 发现可以把常数变大一倍把左边区间扩大一点。
$12:20$ 过了，前 7 个大样例都是一秒多，第 8 个大样例 2.2s。
$12:21$ 卡常。
$12:22$ 卡常。
$12:23$ 卡常。
$12:24$ 卡常。
$12:25$ 卡常。
$12:26$ 卡常。
$12:27$ 卡常。
$12:28$ 卡常。
$12:29$ 卡常。
$12:30$ 卡常。
$12:40$ 卡常，彻底倒闭，只能卡到 $2.0s$，尝试询问监考老师 cpu 型号监考老师说不能给提示。
（比赛完了才知道单调队列又难写又常数大，写个 st 表随手过了）
$12:41$ 肉眼检查。
$12:42$ 肉眼检查。
$12:43$ 肉眼检查。
$12:44$ 肉眼检查。
$12:45$ 肉眼检查。
$12:46$ 肉眼检查。
$12:47$ 测样例。
$12:48$ 测样例。
$12:49$ 测样例。
$12:50$ 测样例。
$12:51$ 测样例。
$12:52$ 测样例。
$12:53$ 测样例。
$12:54$ 测样例。
$12:55$ 测样例。
$12:56$ 测样例。
$12:57$ 急。
$12:58$ 急。
$12:59$ 急。
$13:00$ 结束了，但没看见代码长度。
$13:05$ 看见了。
376，疑似非常高，别挂就好。
----
感觉我在场上会理所当然的认为一些一看就没道理的东西有道理，比如说单调队列比 st 表查 n 次快，还有当年 recall 保证 $a_i$ 互不相同，要求区间 $\{a_i\}$ 的并集，我认为不得不写分块 st 表维护，于是最终倒闭了。