专栏文章

题解：跳跃（jump）

666xyyd
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio03p1t
此快照首次捕获于
2025/12/02 11:10
3 个月前
此快照最后确认于
2025/12/02 11:10
3 个月前
查看原文
证明：cyq讲的是人话。
链接：https://www.mxoj.net/problem/P110121?contestId=173。

题意

有一个长度为 nn 的路面，路面有颜色 00 和 11。如果你在点 ii，那么下一步到达的点 jj 要满足 ∣i−j∣≤k|i-j| \le k。有 qq 次询问，问从 aa 到 bb 最少需要跨过多少个黑色路面。在一些数据点中，还要求出：在最小化跨过的黑色路面情况下，最小化走的步数。

题解

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

弱化版

先做弱化版：假设 a=1a=1。
显然我们可以把距离预处理出来。定义 dpi=(di,ti)dp_i=(d_i,t_i) 表示从点 ii 到点 11 最少需要跨过 did_i 个黑色路面，在最少化跨过的黑色路面情况下，走的步数最少是 tit_i。
我们发现：一个点一定不会往右走，而且最优方案一定是从能到达的点钟选取 dpidp_i 最小的那一个（按照字典序规则，就是 dd 更小的就更小，dd 相同的按 tt 更小的就更小）。写出来就是 dpi=walk⁡(min⁡i−k≤j<i(dpj))dp_i=\operatorname{walk}(\min_{i-k \le j<i}(dp_j))。这个 walk⁡\operatorname{walk} 就表示从某个点转移过来过后做的修改。
如果 ii 从 jj 转移过来，我们需要做什么修改呢？tt 表示走的步数，因此无论如何都要加一；dd 表示跨过的黑色路面，只有在 si=0s_i=0 时才会加一。重新写一下转移方程：
(di,ti)=min⁡i−k≤j<i((dj+[si=0],tj+1))(d_i,t_i)=\min_{i-k \le j<i}((d_j+[s_i=0],t_j+1))
这个可以用单调队列优化做到 O(n)O(n)。

拓展

我们直观上认为，这两种方式差不太多：
  • 从 bb 走到 aa。
  • 从 bb 走到 11，但是节省从 aa 走到 11 的路程。 也就是说，所求的答案和 (db−da,tb−ta)(d_b-d_a,t_b-t_a) 差不多。对比样例可得，第一个 dd 是一模一样的，而且第二个 tt 与答案的差要么是 00，要么是 11。
这个 11 差在哪里呢？原来，我们的程序无法区分 tit_i 相同的情况。
从刚才的对比来看，从 bb 跳到 aa 的最短路径和从 bb 跳到 11 的最短路径差不太多。我们可以让 bb 跳到 ti=tat_i=t_a 的位置，然后看是否需要再额外跳一次。
这是因为，如果某次询问的 a′=ia'=i，那么 tb−tat_b-t_a 的结果和 tb−ta′t_b-t_{a'} 的结果将会相同，程序就不知道还要额外跳多少步。
但是我们知道从 bb 跳到 ii 肯定要 tb−tit_b-t_{i} 步，那剩下的要不要额外跳不就看 ∣i−a∣≤k|i-a| \le k 了吗？
然后跳的过程可以倍增，就做完了。

评论

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

正在加载评论...