专栏文章

NOIP2025 个人题解 - LCA

CCommonAnts管理员
算法·理论参与者 97已保存评论 100

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
100 条
当前快照
3 份
快照标识符
@miotrad2
此快照首次捕获于
2025/12/03 01:01
3 个月前
此快照最后确认于
2025/12/25 01:30
2 个月前
查看原文

NOIP2025 个人题解

作者：LCA 蔡德仁 CommonAnts
特别感谢助教 @_ 协助验证细节，写暴力等。⁢

评

总体难度：
  • T1 黄/绿
  • T2 上位蓝/下位紫
  • T3 黑
  • T4 上位紫/下位黑
分项：
  • T4 原题度偏高，q=1q=1 情况是 LOJ6490
  • T3 需要一点注意力
  • T2 T3 相对 NOIP 来说比较多数学细节硬推导，尤其是 T3
  • T2 T3 T4 算法细节相对 NOIP 来说都比较多
  • T4 相对 NOIP 来说代码细节比较多

T1 糖果店 / candy

思路和算法

如果 xi=yix_i=y_i 那么我们只会买最便宜的。带着这个直觉考虑奇偶性不同的情况。
每个糖果可以拆成两种糖果：
  • 个数 22，价格 xi+yix_i+y_i，无限购买。
  • 个数 11，价格 xix_i，只能买一个。
对于只能买一个的这部分，既然个数都是 11，肯定是价格从低到高购买。
对于买两个的这部分，由于是无限的，我们只会买最便宜那种。记 xi+yix_i+y_i 最小的糖果为 aa，若其他糖果购买了 ≥2\ge 2 颗，则将前两颗换为 aa 一定不劣。
因此购买方案一定为购买了若干对糖果 aa，然后再买每种糖果不超过一颗。将 {xi}\{x_i\} 从小到大排序，枚举每个前缀，计算购买一个这些糖果的答案即可。
时间复杂度 O(nlog⁡n)O(n\log n)。
也可以视为背包，f[t]f[t] 表示买 ≥t\ge t 颗糖最小总花费，进行 DP，也能发现对于总个数 ≥n\ge n 的情况值直接等于 f[t]=f[t−2]+min⁡(xi+yi)f[t]=f[t-2]+\min(x_i+y_i)。

T2 清仓甩卖 / sale

思路和算法

对于一种定价方案，假设糖果已经按照性价比降序排序：
考虑最后一颗购买的糖果 aa，若 wa=2w_a=2, 则购买的糖果一定是全局性价比最高的若干颗，且要么 w=1w=1 的买完了要么钱恰好花完了（否则会继续买 w=1w=1 的）。此时一定是最优解。只有 wa=1w_a=1，才可能存在某种替换方案使得原价更高。
具体来说，设按顺序购买了糖果 …,x,…,y,z(wx=wz=1,(∀x<i<z)wi=2)\dots , x, \dots, y, z (w_x=w_z=1, (\forall x\lt i\lt z) w_i=2) 这里 x,y,zx,y,z 分别表示买的倒数第二个 w=1w=1 的糖，买的总倒数第二个糖，以及买的最后一个糖（按上文讨论必须 w=1w=1）。可能 x=yx=y（买的最后两个都是 w=1w=1），也可能 zz 不存在（钱恰好剩 11 时 w=1w=1 的买完了）。需要满足 ∑i≤ywi=m−1\sum_{i\le y} w_i = m-1。
设 y+y+ 表示性价比排在 yy 后面没选的 w=2w=2 的糖果里最大的。若 ax+az<ay+a_x+a_z\lt a_{y+}，那么将 x,zx, z 替换为 y+y+ 可以使原价总和更大，否则这种方案一定最优.
将 {(ai,wi)}\{(a_i, w_i)\} 按性价比排序，枚举 x≤yx\le y，此时让 ∑i≤ywi=m−1\sum_{i\le y} w_i = m-1 的定价方案可以组合数计算，合法 zz 的选择是一段后缀，双指针统计即可。
细节比较多，x=yx=y（买的最后两个都是 w=1w=1）以及 zz 不存在（钱恰好剩 11 时 w=1w=1 的买完了），注意讨论。好在计数题如果没讨论清楚可以在样例发现。
时间复杂度 O(∑n2)O(\sum n^2)

T3 树的价值 / tree

思路和算法

这是个最优化问题，先考虑最优解长什么样。
观察、调整，可以得到几个基本结论：
  • 不会有祖孙标同样的号。一个数字已经让它到根路径点的数字集合都有这个数了，祖先再这么干就浪费了。
  • 不会有祖先比子孙标号小。在上一条基础上容易发现这一点。
  • 每个点只有两种可能的决策，要么让自己的答案变大，要么给祖先产生贡献，否则肯定浪费。
  • 进一步地，我们可以把每个点标为黑白两种颜色之一，分别表示答案变大（mex\mathrm{mex} 比每个儿子的都大）的点以及答案不变大（mex\mathrm{mex} 等于儿子的最大值）的点，然后自底向上决策。可以归纳证明对于特定的染色方案，最优解就是把每个白点分给祖先里最近的黑点（否则不如把最近的黑点也变白一起向上贡献），然后遇到黑点时它的 mex\mathrm{mex} 是子树内所有黑点 mex\mathrm{mex} 最大值加上分给它的白点个数再 +1+1（它自己的贡献。）。
明显可以自底向上递推，比如我们可以设计一个暴力 DP：b[u][i][j]b[u][i][j] 表示子树 uu 中，ii 个贡献到 uu 以上的白点，黑点 mex\mathrm{mex} 最大值为 jj 的情况下最大子树内 mex\mathrm{mex} 总和。这可以优化转移到 O(n3)O(n^3) 的。有 5050 到 7070 分。
怎么优化呢？我们继续考虑最优解的结构，可以发现更多性质：
  • 每个黑点必然有至少一个黑儿子。如果一个黑点 uu 全是白儿子，我们找到它子树内所有黑点 mex\mathrm{mex} 最大的 vv，通过重排分给 uu 的白点可以让子树内黑点值都不变的情况下 vv 到 uu 路径都变成黑点，这一定更优。如果子树内全是白点则要么这个黑点本身变白更优，要么仍然前述更优。
  • 所以，把每个黑点和它继承的黑儿子连起来，有一个链剖分结构。我们设每个点的重儿子是它所有儿子中 mex\mathrm{mex} 最大的那个，这也是它最大的黑儿子。
  • 每个黑点都有黑色重儿子，所以链都是直通叶子的，每个链都是上白下黑。
  • 可以发现每个黑点的 mex\mathrm{mex} 就等于它所属链往下的黑点个数，加上这些点的轻儿子向下连通的连续白点个数之和。白点的 mex\mathrm{mex} 等于重儿子的。
  • 我们发现在这个链剖分结构上，贡献可以拆分给各个链。点的贡献，是祖先中第一个黑点在自己链的深度。所有贡献都可以在链之间的树上自底向上统计。
那么我们考虑改为这个状态 DP：尝试设 f[L]f[L] 表示当前考虑了重链 LL 和重链 LL 所有子树的情况下的最优解。这个状态数（树上可能的祖孙链数）是 O(nm)O(nm) 的，然而我们只能统计子树内祖先有黑点的点的贡献。
因此状态需要记录中间值 g[u][i]g[u][i] 表示考虑了子树 uu，并且 uu 向上的贡献系数（祖先中第一个黑点在自己链的深度）为 ii 情况下的最优贡献。转移时统计所有祖先中第一个黑点在 LL 上的点的贡献。现在我们的目的是优化转移。
gg 的转移需要枚举 uu 链向下的第一个黑点，也就是枚举 uu 向下到 vv 的一条链。这条链的一个到 uu 距离 dd 的点分支出的孩子 xx 的贡献是 g[x][max⁡(d,i)]→g[u][i]g[x][\max(d,i)]\to g[u][i]，然后 gg 的值是所有 vv 对应的值取最大值。这个可以用数据结构维护每种深度的贡献来统计。
时间复杂度：O(nmlog⁡n)O(nm\log n)
使用长链剖分优化可以做到理论上 O(nm)O(nm)。
一开始的时候以为的 O(nm)O(nm) 转移是想简单了。这个问题的确有子树 uu 内在不知道其余部分的情况下可能成为最优子结构的本质不同极优解个数不超过 min⁡(sz,dep)\min(sz,dep)（子树大小和 uu 到根深度）的性质。但是转移合并是链合并不是儿子合并，所以和树形背包的复杂度分析结论不同。直接维护转移的复杂度会退化到 O(min⁡(n2,nm2))O(\min(n^2,nm^2))，只能得 8080 分。
能否继续挖掘子树最优决策性质，快速找到子树最优决策，从而优化枚举链的转移复杂度？比如说贪心微调或者决策单调性之类的？

T4 序列询问 / query

思路和算法

问题问的是：每个合法区间的区间和，分别贡献到区间内每个位置 ii 上，问每个位置被贡献的最大值。其中，合法区间，指的是区间长度在给定范围内的所有区间。
数据范围允许 O(nq)O(nq) 的时间复杂度，所以先不用考虑强行维护修改，还是先每次询问把每个 ii 答案算出来。
那么这里关键的是所有合法区间的整体结构。画到平面上，可以发现是一个斜条带：
怎么统计这个呢？这种梯形区间集合是比较难统计的，我们统计只有一侧长度限制还行，两侧限制就比较难。所以划分一下：
把合法区间集合划分成若干个三角形统计。这些三角形中每一个实际上都是两种形式之一：
  • 某个给定区间 [L,R][L,R] 的子区间，且长度 ≥C\ge C。
  • 某个给定区间 [L,R][L,R] 的超区间，且长度 ≤C\le C。
这两种情况的贡献，可以枚举 [L,R][L,R] 和被统计的区间之差，这个差可以刻画为从 [L,R][L,R] 向内或向外两侧的前缀/后缀的贡献。我们直接枚举前缀，则对应的满足长度的后缀范围单调，双指针计算贡献和覆盖。
具体来说：
  • 某个给定区间 [L,R][L,R] 的子区间，且长度 ≥C\ge C。
    • 当 CC 大于区间长度一半，设区间中点（或者第 CC 个点也行）为 mm，必经 mm。
      • 对于这种情况，我们设一个要统计的区间是 [l,r](l≤L≤R≤r)[l,r] (l\le L\le R\le r)。那么它可以被视为减去前缀 [L,l)[L,l) 再减去前缀 (r,R](r,R] 再加上固定的 [L,R][L,R]。后缀和前缀的总长度不超过某个定值。
      • 首先预处理每个前缀和后缀的最小后缀和/前缀和。
      • 枚举每个 ll，查出这个 ll 对应的所有可能 rr 的最大区间和，并且贡献给 (l,m](l,m]。
      • 枚举每个 rr，查出这个 rr 对应的所有可能 ll 的最大区间和，并且贡献给 (m,r)(m,r)。
      • 再枚举每个 l,rl,r，把上述 (l,m](l,m] 和 (m,r)(m,r) 的贡献实际贡献到每个位置。
    • 否则，每隔 CC 个选一个关键点 m1,m2,…m_1,m_2,\dots ，区间至少经过一个关键点。枚举第一个经过的关键点统计区间，统计方法仍然类似。
    • 分两种情况处理是为了保证 CC 较大但 CC 和区间长度差距小时，复杂度是正确的和区间长度减 CC 同阶，而不是区间长度同阶。你也可以认为其实都是每隔 CC 个选一个关键点，但处理方法还是要分类。
  • 某个给定区间 [L,R][L,R] 的超区间，且长度 ≤C\le C。
    • 对于这种情况，我们设一个要统计的区间是 [l,r](l≤L≤R≤r)[l,r] (l\le L\le R\le r)。那么它可以被视为后缀 [l,L)[l,L) 拼接上前缀 (R,r](R,r] 再加上固定的 [L,R][L,R]。后缀和前缀的总长度不超过某个定值。
    • 首先预处理每个前缀和后缀的最大后缀和/前缀和。
    • 枚举每个 ll，查出这个 ll 对应的所有可能 rr 的最大区间和，并且贡献给 [l,L)[l,L)。
    • 枚举每个 rr，查出这个 rr 对应的所有可能 ll 的最大区间和，并且贡献给 (R,r](R,r]。
    • 再枚举每个 l,rl,r，把上述 [l,L)[l,L) 和 (R,r](R,r] 的贡献实际贡献到每个位置。
    • 把上面所有的贡献的最大值贡献给 [L,R][L,R]
时间复杂度和贡献区间个数是 O(∣(R−L)−C∣+1)O(\lvert (R-L)-C\rvert+1) 的，也就是不超过图上红线段长度。所有小三角形加起来的红线段长度是 O(n)O(n) 的，故总时间 O(n)O(n)。
然后算答案。上面的统计我们一共给出了 O(n)O(n) 个贡献区间，现在还要对于每个位置计算所有覆盖它的贡献区间的最大值。直接枚举端点，单调栈维护即可。
总之这个问题的关键是采样法，即找到一些关键点，满足定长度限制的区间一定经过这些关键点，然后拆分前后缀进行统计。直接进行倍增采样（倍增值域分块）也可以做。
q=1q=1 时有原题 LOJ6490，不过网上的题解通常带 log⁡\log。
注意统计过程中需要 O(1)O(1) 查区间最值，这个 O(nlog⁡n)O(n\log n) 预处理一下就行。
题目能不能更优化呢？是困难的。输入一个长为 nn 值域较大的数列，对于每个 1≤i≤n1\le i\le n 求所有长度 ii 区间和的最值，这个问题可以归约大值域单调序列 max⁡,+\max,+ 卷积（中间放一个巨大数保证选了，然后把两个序列底对底延伸两侧即可），目前不能多项式低于 22 次方。
时间复杂度：O(nlog⁡n+nq)O(n\log n+nq)
采用较好的统计顺序可以不用维护任意区间最值查询，都改用单调队列等统计，可以改进到单纯的 O(nq)O(nq) 时间。

题外话

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

  • R183. 带长度限制的区间统计（条状/梯形分治） - Guoyh ← liaoz123
  • R276. 定长分块（定距采样法） - nzhtl1477
  • R528. 倍增值域分块（倍增采样法） - 「佚名」

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

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

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

评论

共 100 条评论，欢迎与作者交流。

正在加载评论...