NOIP2025 游记

· · 生活·游记

开题，大概看了一眼题，发现题目类型和去年的题目类型完全一致。（贪心/基础模拟，计数，神秘树上题，弱智数据结构）

去年的我栽在了 T4 差一步想出来，感觉这是给我的第二次机会（

好的先看 T1，好难我不会咋办，一会儿想到简单贪心，8 分钟过大样例。

（考后有人说这题有个特判大样例没卡，想了一下好像写了，希望是吧）

然后开始做 T2，好难我不会咋办。想到可以先考虑 m = 2 的情况，发现特殊性质也有这个，笑了。

之后还要找前面另一个点使得和贪心选的点加起来不能大于失败的点，大概就是这样。 $20 mins$ 写，然后犯了两个沙币错误 ($\binom m n$ 写成 $fac_n \times fac_m \times fac_{n - m}$，$continue$ 写成 $break$)，调了很久。 这是立方的做法，接下来想平方，又愣了 $20 mins$，发现 $\binom k x \times \binom {n - k} y$，$k$ 从 $1$ 扫到 $x$，这个玩意儿不就是 $\binom n {x + y}$吗。 改完之后过不了大样例，发现没判负数，又浪费 $10mins$，写完到 $10：40$。 此时面临着和去年一样的决策，是去做手玩的题，还是去做数据结构题。 吸取去年的教训，我打算先打 $T3$ 的 $16$ 分暴力再走人，幸运的是，$20 mins$ 打完没挂。 接下来来到 $T4$，发现这个题并不像去年的那个题那么简单，硬是瞪着前三个测试点看了很久都不会。。。 算了，先从特殊性质入手吧，发现性质 $B$，区间长度小于等于 $32$ 简直就是送分，先把所有区间拿出来，再预处理包含每个点且长度为 $L$ 的区间和最大值。 接着对于每个点预处理任意两个端点形成的区间最大值 ($32 \times 32 \times n$)，询问 $O(qn)$，正好过，发现内存没炸。 然后看到特性 $A$，$L = R$，发现可以单调队列，火速写掉一遍过。 接下去发现第 $1$ 个点就是单调队列跑 $n$ 遍，然后 $23$ 的话，对于每个位置的答案进行分块，查询可以做到 $O (qn^2 / b)$，于是火速又写掉。 然后我发现 $T4$ 没有办法再拿更多分了，此时还剩 $30 mins$ 左右，来到 $T3$ 想再骗点分。 $T3$ 一开始想的是 $n = 13$ 爆搜剪枝随便写写，然后发现剪不了，于是乱写劣质 $DP$。 写完之后发现 $n = 13$ 的点过不了，把循环倒着写，$5$ 个点挂了 $1$ 个但是没时间了所以到此为止。 $100 + 100 + [16, 48] + 40