NOIP 2025 题解

· · 个人记录

一个月没做题了，手感全无，哎。

可能要挂很多分，我无话可说。

T1

拆分成：代价为 x_i 的一个糖果，与代价为 x_i+y_i 的无限个糖果。贪心选择 x 最小的若干糖果与 x_i+y_i 最小的糖果即可。

T2

考虑什么时候不优。也就是，你有一个大小为 2 的放不进去跳过（但实际上把某个大小为 1 的扔掉你就能放进去了）。

考虑枚举这个 2 与这个 1，然后发现贡献是一堆组合数和 2 的幂，容易做到 O(n^2)。

T3

【不确定算法正确性，但是他通过了所有大样例】

类似费用延迟计算的想法，如果子树的 mex 为 v，那么其中所有 >v 的数我们不需要知道具体值，我们称之为自由量。

然后调整法弄一下发现，每个点它的 mex，主要取决于它的某个儿子——也就是说，最优情况下每个点的 mex 将会是它某个儿子的 mex 加上一些东西。这样把每个点和他的关键儿子配对，得到了一个树剖分。

树剖分的好处是，虚边是无用的，我们可以直接断掉。然后每个点它会在其某个祖先处从无用点变成有用点，它的贡献为——将某条实链的一个前缀的 mex 全部加 1。

我们可以快乐的树上 DP 了，复杂度 O(nm \log n)。

T4

首先，如果 r \le 2l，存在一个显然的做法：i 到左右某个端点的距离一定 \le l，那么我们对每个 j 计算以他为左端点的符合要求的子段的最大权值 m_j，让 res_i 对 \max_{i-l+1 \le j \le i} m_j 取 \max 即可，然后翻转序列再做一次。

因此我们可以把 [l,r] 拆成 [l,2l]、[2l+1,4l+3]、\cdots，这样在 O(nq \log n) 的复杂度内解决了本题。

进一步的，预处理 l=2^k,r=2^{k+1} 的答案，就可以做到 O(nq)。

过不去，妈的。