题解：AT_mujin_pc_2017_c Robot and String

Swirling · 2026-08-11 18:21:45 · 题解

这真是紫吗？为什么我可以 40min 切掉？下文用 0 \sim 25 代指 a \sim z，26 代指空。

我们想在区间 [l, r] 内凑出 y，一定是形如以下形态：

显然中间的 [x, y) 位置都可以划归到子问题。那么考虑 dp，设 f_{i, c} 为满足区间 [i, X) 可以凑出字符 c 的最小 X，有初始值 f_{i, s_i} = i + 1。可以轻松列出转移：f_{i, c} = \min(f_{i, c}, f_{f_{i, c - 1}, c - 1})。

不过这样会挂，原因是当我们组出 26 时，中间一段直接消失了，那么 26 左侧的段可以继承自右侧，也就是说：

至此我们求出了所有 i 的、后继的、可以组出 26 的位置 f_{i, 26}。显然可以倍增记 g_{i, k} 为 i 往后跳 2^k 次 f_{i, 26} 所到的位置。查询时跳一下即可。

时间复杂度 \mathcal{O}(nV + (n + q)\log n)，足以通过此题。