做题记录 25.8.26

szt100309 · 2025-08-26 10:25:08 · 个人记录

\purple\odot LOJ #4261. 「KTSC 2024 R2」跳跃游戏 \quad P11239 [KTSC 2024 R2] 跳跃游戏

显然可以转化为 a_{0\sim n-1} 中选择若干个数满足任意两个选择的位置之间距离不小于 k，最大化选出的数的和

令 f_i 表示 a_{0\sim i} 的答案，则转移为 f_i=\max f_{0\sim i-k}+a_i

考虑每次处理一段，从 f_{uk-k}\sim f_{uk-1} 转移到 f_{uk}\sim f_{uk+k-1}，令 pmx 为 f_{0\sim uk-k-1} 中的最大值

初始 pmx=0，u=0，令 p_i=f_{uk-k+i}，c_i=f_{uk+i}，a_i 为原本的 a_{uk+i}，则 p_{0\sim k-1}\gets -\infty

则转移为

c_i=\max(pmx,p_{0\sim i})+a_i

假定 p_{-1}=pmx 则化为

c_i=\max(p_{-1\sim i})+a_i

考虑当前范围中存在一次 a 区间加的左端点 l，下一个左端点为 l_2，则可证 a_{l\sim l_2-1} 中只需要保存 a_l（若 l=l_2 则忽略，即去重左端点）

扫描一遍当前区间内的端点得到 a 极长等值段，从而将 +a_i 转化为若干区间加，在所有区间加之前更新 c_i=\max (p_{-1\sim i})，以上操作容易线段树维护

这样时间复杂度为 O(q\log q+\frac nk)

若存在连续若干段中的 a 都相同，则可以转化为 p_{-1} 和 p_{0\sim k-1} 的修改

这样时间复杂度为 O(q\log q)

LOJ \quad luogu

参考

考虑对于一个确定的序列 a_{1\sim n} 如何求解

将 a 中极长等值区间缩为一个二元组 (v,c) 表示有 c 个 v

考虑连续三个 (v_1,c_1),(v_2,c_2),(v_3,c_3)，满足 v_1>v_2<v_3，则 v_1 和 v_3 要并起来 v_2 必须和并至 \min(v_1,v_3)

令 d=\min(v_1,v_3)-v_2，则 2^d 个 v_2 可以合并出一个 \min(v_1,v_3)

若 2^d\mid c_2 则直接将 (v_2,c_2) 替换为 \left(\min(v_1,v_3),\frac{c_2}{2^d}\right)

否则 v_1 和 v_3 无法合并，将序列从 (v_2,c_2) 处断开，左右分别放回一个 \left(\min(v_1,v_3),\left\lfloor\frac{c_2}{2^d}\right\rfloor\right)

经过若干次以上操作，剩下的每一段都是严格单峰的，长度为 O(V)（令 V=\max a=10）

用 (+\infty，\ge 1) 表示断点，起点，终点，继续消去谷，同时在消去 (v_2,c_2) 时将 v_2+\left\lfloor\log_2 c_2\right\rfloor 计入答案，则最终得到一个 (+\infty,\ge 1) 且在合并过程中得到答案

用线段树维护每个区间内的二元组序列，则时间复杂度为 O(Vn\log n)，空间复杂度 O(Vn)

LOJ \quad luogu

参考

显然回到父亲不优

二分答案，转化为判定取 k 时是否满足要求

令 f_u 表示 u 已经染黑的情况下，在进入子树 u 之前最少需要染黑的点的数量，使得进入子树 u 后合法

显然转移为 f_u=\max(0,\sum_{v\in son(u)}(f_v+1)-k)

若 f_1=0 则当前 k 合法

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

代码

显然答案的上限为 A 和 B 中连通块数量的较小值减一，以下通过构造证明能取道这一上界

先枚举 2\le i\le n，若 A 和 B 中 1 和 i 都不连通，则选择边 (1,i)，并在 A 和 B 中都将 1 和 i 合并，显然这部分选边一定合法

令 L 为 A 中不与 1 连通的点的集合，R 为 B 中不与 1 连通的点的集合（将 i 加入 L 后需要合并 1,i 再继续查找，即每个连通块只能选择至多一个点，R 同理，显然 L\cap R=\mathbb\emptyset）

在 L 和 R 中分别选择 \min(|L|,|R|) 个，然后依次匹配即可

显然合法（选择 (u,v)\mid u\in L,v\in R 时，A 中 u 和 1 不连通但 B 中连通，v 中同理，显然满足要求）且数量达到上界

时间复杂度 O((n+m_1+m_2)\alpha(n))

代码

参考