NOIP 2025 消愁记

· · 生活·游记

如此成绩，如何 CTT？

小趋势：早上进场的时候由于导航到了错误的门因此绕着学校走了一圈才进去，8:26 进入的机房。

开 T1，反正脑子不是很清醒，写了个暴力枚举多次选的位置，然后二分两下，大样例没过，多枚举了两个出现次数，大样例过了，不放心上了拍子，差不多 30min 吧。

然后开 T2，发现是计数，想了一下判定方式发现如果有一个时刻只有 2 的代价了，但是我按照性价比选了两个 1，亏掉了中间一个 2 就可能会亏。

这样一想感觉统计不合法的贡献是比较容易的，枚举被忽略的 2 以及旁边两个 1，直接就是 O(n^3) 做法。

又想了一下范德蒙德卷积就好了，O(n^2) 写完，调了一会过了大样例，大概用了 40min，感觉大样例挺强就没拍。

然后开 T3，上来看到子树 mex 知道做过 qoj9614，不过一开始没想起来结论是啥，然后先写了个 O(n^3) 纯暴力，然后又想了有 20min 结合推导推出了结论，又 20min 过后想出了 O(nd^2) 做法。

然后想了一下，决定继续想正解，看着这个 d\leq 800 感觉很奇怪，直接上手优化 O(nd^2) 的话看上去有点麻烦，半个小时之后终于发现了可以再开一个 dp 数组记录下层，上层对每个 d 开树状数组就可以了。

赶紧开写，写了半个小时过了大样例，总共花了挺长时间的，只有不到一个半小时了。

开 T4，感觉很紧张，一下就会了 D 性质，但是没有发现拓展，也没有想到对倍增分块，然后还是不会做。

过了半个小时我感觉得写历史最值了，不然根本没分，写到一半的时候我突然想到了 E 性质怎么做，直接 L 个分一块就容易做到单次 O(n(\log n+\frac{R}{L}))（这里是因为我是区间取 max 更新的，没有发现直接滑动窗口就去掉 \log 了，还是实力不行），立刻得到了一个单次询问 O(n\log n\log_{15}n) 的做法，常数很小，直接开始写，还剩 15min 的时候调过了大样例，有两个要跑 5s，其余的都 \leq 1.5s，数了一下部分分表大概有 60\sim 70 分。

然后我突然就想到了一个复杂度是 O(qn(\log n+\log q) 的奇异搞笑做法，不过我认为常数很小能过（先离散化跑出每一段的答案，然后对询问猫树分治），感觉能写完就开冲。

然后这里我就犯了一个错，我先入为主认为这种 ds 题一定会给 1G 空间，然后我算了一下需要开 2nq 的 long long（真有你的，\sum a_i\leq 5\times 10^9），发现是 800MB，由于时间不够了被 ak 蒙蔽了双眼所以直接开冲，在 12:58 的时候通过了大样例，测大样例 8 发现是 1.1s，直接交上去了，最后差点没交上文件。

然后我在 windows 下打开 pdf 一看，发现空间是 512MB，哎，也没啥好说的，就是贪了。

前面三个题会不会挂还不知道。