题解：跳跃（jump）

66xyyd · 2025-09-06 10:26:45 · 个人记录

证明：cyq讲的是人话。

链接：https://www.mxoj.net/problem/P110121?contestId=173。

题意

有一个长度为 n 的路面，路面有颜色 0 和 1。如果你在点 i，那么下一步到达的点 j 要满足 |i-j| \le k。有 q 次询问，问从 a 到 b 最少需要跨过多少个黑色路面。在一些数据点中，还要求出：在最小化跨过的黑色路面情况下，最小化走的步数。

题解

如果 a>b，就交换 a 和 b，这是因为往左走和往右走是对称的。

弱化版

先做弱化版：假设 a=1。

显然我们可以把距离预处理出来。定义 dp_i=(d_i,t_i) 表示从点 i 到点 1 最少需要跨过 d_i 个黑色路面，在最少化跨过的黑色路面情况下，走的步数最少是 t_i。

我们发现：一个点一定不会往右走，而且最优方案一定是从能到达的点钟选取 dp_i 最小的那一个（按照字典序规则，就是 d 更小的就更小，d 相同的按 t 更小的就更小）。写出来就是 dp_i=\operatorname{walk}(\min_{i-k \le j<i}(dp_j))。这个 \operatorname{walk} 就表示从某个点转移过来过后做的修改。

如果 i 从 j 转移过来，我们需要做什么修改呢？t 表示走的步数，因此无论如何都要加一；d 表示跨过的黑色路面，只有在 s_i=0 时才会加一。重新写一下转移方程：

这个可以用单调队列优化做到 O(n)。

拓展

我们直观上认为，这两种方式差不太多：

• 从 b 走到 a。
• 从 b 走到 1，但是节省从 a 走到 1 的路程。 也就是说，所求的答案和 (d_b-d_a,t_b-t_a) 差不多。对比样例可得，第一个 d 是一模一样的，而且第二个 t 与答案的差要么是 0，要么是 1。

这个 1 差在哪里呢？原来，我们的程序无法区分 t_i 相同的情况。

从刚才的对比来看，从 b 跳到 a 的最短路径和从 b 跳到 1 的最短路径差不太多。我们可以让 b 跳到 t_i=t_a 的位置，然后看是否需要再额外跳一次。

这是因为，如果某次询问的 a'=i，那么 t_b-t_a 的结果和 t_b-t_{a'} 的结果将会相同，程序就不知道还要额外跳多少步。

但是我们知道从 b 跳到 i 肯定要 t_b-t_{i} 步，那剩下的要不要额外跳不就看 |i-a| \le k 了吗？

然后跳的过程可以倍增，就做完了。