NOIP2025 个人题解 - LCA

· · 算法·理论

NOIP2025 个人题解

作者：LCA 蔡德仁 CommonAnts

特别感谢助教 @_ 协助验证细节，写暴力等。⁢

评

总体难度：

分项：

T1 糖果店 / candy

思路和算法

如果 x_i=y_i 那么我们只会买最便宜的。带着这个直觉考虑奇偶性不同的情况。

每个糖果可以拆成两种糖果：

对于只能买一个的这部分，既然个数都是 1，肯定是价格从低到高购买。

对于买两个的这部分，由于是无限的，我们只会买最便宜那种。记 x_i+y_i 最小的糖果为 a，若其他糖果购买了 \ge 2 颗，则将前两颗换为 a 一定不劣。

因此购买方案一定为购买了若干对糖果 a，然后再买每种糖果不超过一颗。将 \{x_i\} 从小到大排序，枚举每个前缀，计算购买一个这些糖果的答案即可。

时间复杂度 O(n\log n)。

也可以视为背包，f[t] 表示买 \ge t 颗糖最小总花费，进行 DP，也能发现对于总个数 \ge n 的情况值直接等于 f[t]=f[t-2]+\min(x_i+y_i)。

T2 清仓甩卖 / sale

思路和算法

对于一种定价方案，假设糖果已经按照性价比降序排序：

考虑最后一颗购买的糖果 a，若 w_a=2, 则购买的糖果一定是全局性价比最高的若干颗，且要么 w=1 的买完了要么钱恰好花完了（否则会继续买 w=1 的）。此时一定是最优解。只有 w_a=1，才可能存在某种替换方案使得原价更高。

具体来说，设按顺序购买了糖果 \dots , x, \dots, y, z (w_x=w_z=1, (\forall x\lt i\lt z) w_i=2) 这里 x,y,z 分别表示买的倒数第二个 w=1 的糖，买的总倒数第二个糖，以及买的最后一个糖（按上文讨论必须 w=1）。可能 x=y（买的最后两个都是 w=1），也可能 z 不存在（钱恰好剩 1 时 w=1 的买完了）。需要满足 \sum_{i\le y} w_i = m-1。

设 y+ 表示性价比排在 y 后面没选的 w=2 的糖果里最大的。若 a_x+a_z\lt a_{y+}，那么将 x, z 替换为 y+ 可以使原价总和更大，否则这种方案一定最优.

将 \{(a_i, w_i)\} 按性价比排序，枚举 x\le y，此时让 \sum_{i\le y} w_i = m-1 的定价方案可以组合数计算，合法 z 的选择是一段后缀，双指针统计即可。

细节比较多，x=y（买的最后两个都是 w=1）以及 z 不存在（钱恰好剩 1 时 w=1 的买完了），注意讨论。好在计数题如果没讨论清楚可以在样例发现。

时间复杂度 O(\sum n^2)

T3 树的价值 / tree

思路和算法

这是个最优化问题，先考虑最优解长什么样。

观察、调整，可以得到几个基本结论：

明显可以自底向上递推，比如我们可以设计一个暴力 DP：b[u][i][j] 表示子树 u 中，i 个贡献到 u 以上的白点，黑点 \mathrm{mex} 最大值为 j 的情况下最大子树内 \mathrm{mex} 总和。这可以优化转移到 O(n^3) 的。有 50 到 70 分。

怎么优化呢？我们继续考虑最优解的结构，可以发现更多性质：

那么我们考虑改为这个状态 DP：尝试设 f[L] 表示当前考虑了重链 L 和重链 L 所有子树的情况下的最优解。这个状态数（树上可能的祖孙链数）是 O(nm) 的，然而我们只能统计子树内祖先有黑点的点的贡献。

因此状态需要记录中间值 g[u][i] 表示考虑了子树 u，并且 u 向上的贡献系数（祖先中第一个黑点在自己链的深度）为 i 情况下的最优贡献。转移时统计所有祖先中第一个黑点在 L 上的点的贡献。现在我们的目的是优化转移。

时间复杂度：$O(nm\log n)

使用长链剖分优化可以做到理论上 O(nm)。

一开始的时候以为的 O(nm) 转移是想简单了。这个问题的确有子树 u 内在不知道其余部分的情况下可能成为最优子结构的本质不同极优解个数不超过 \min(sz,dep)（子树大小和 u 到根深度）的性质。但是转移合并是链合并不是儿子合并，所以和树形背包的复杂度分析结论不同。直接维护转移的复杂度会退化到 O(\min(n^2,nm^2))，只能得 80 分。

能否继续挖掘子树最优决策性质，快速找到子树最优决策，从而优化枚举链的转移复杂度？比如说贪心微调或者决策单调性之类的？

T4 序列询问 / query

思路和算法

问题问的是：每个合法区间的区间和，分别贡献到区间内每个位置 i 上，问每个位置被贡献的最大值。其中，合法区间，指的是区间长度在给定范围内的所有区间。

数据范围允许 O(nq) 的时间复杂度，所以先不用考虑强行维护修改，还是先每次询问把每个 i 答案算出来。

那么这里关键的是所有合法区间的整体结构。画到平面上，可以发现是一个斜条带：

怎么统计这个呢？这种梯形区间集合是比较难统计的，我们统计只有一侧长度限制还行，两侧限制就比较难。所以划分一下：

把合法区间集合划分成若干个三角形统计。这些三角形中每一个实际上都是两种形式之一：

这两种情况的贡献，可以枚举 [L,R] 和被统计的区间之差，这个差可以刻画为从 [L,R] 向内或向外两侧的前缀/后缀的贡献。我们直接枚举前缀，则对应的满足长度的后缀范围单调，双指针计算贡献和覆盖。

具体来说：

时间复杂度和贡献区间个数是 O(\lvert (R-L)-C\rvert+1) 的，也就是不超过图上红线段长度。所有小三角形加起来的红线段长度是 O(n) 的，故总时间 O(n)。

然后算答案。上面的统计我们一共给出了 O(n) 个贡献区间，现在还要对于每个位置计算所有覆盖它的贡献区间的最大值。直接枚举端点，单调栈维护即可。

总之这个问题的关键是采样法，即找到一些关键点，满足定长度限制的区间一定经过这些关键点，然后拆分前后缀进行统计。直接进行倍增采样（倍增值域分块）也可以做。

注意统计过程中需要 $O(1)$ 查区间最值，这个 $O(n\log n)$ 预处理一下就行。 题目能不能更优化呢？是困难的。输入一个长为 $n$ 值域较大的数列，对于每个 $1\le i\le n$ 求所有长度 $i$ 区间和的最值，这个问题可以归约大值域单调序列 $\max,+$ 卷积（中间放一个巨大数保证选了，然后把两个序列底对底延伸两侧即可），目前不能多项式低于 $2$ 次方。 时间复杂度：$O(n\log n+nq)

采用较好的统计顺序可以不用维护任意区间最值查询，都改用单调队列等统计，可以改进到单纯的 O(nq) 时间。

题外话

知识点征集项目中 NOIP2025 T4 序列询问 / query 的技巧内容：

更多知识请看 知识点征集速报!!!! 第二期（2025.11.12-11.16） - 星语社Σ*

来参与征集！ 有奖征集 OI 小知识点，思考题和科普

个人著作权声明：严禁任何未经本人（刘承奥，常用笔名/网名：蔡德仁 CommonAnts LCA liu_cheng_ao）书面授权者在梦熊联盟，或者任何虚假宣传或不实营销炒作或不正当竞争行为严重的 OI 机构的课程内或交流平台（包括但不限于品牌集训线下讨论，交流群，OJ，公众号，视频号等）上引用、传播、讨论此内容，以及本人于2024年5月及之后发布的所有内容，包括声明为公开的内容在内。