CF1860E 题解

· · 题解

没场切。/ng

考虑将原问题转成：

给长度为 n 的序列 a_{1 \sim n}，你要从 x 位置走到 y 位置，每次你可以走到相邻位置，或走到与当前位置数字相同的位置，求最少步数。

这是一类经典问题，考虑建图后最短路解决。给每个位置建点 p_i，值域上每个数建点 q_i，然后连 p_{i - 1} \leftrightarrow p_i，边权为 1；连 p_i \to q_{a_i}，边权为 1；q_{a_i} \to p_i，边权为 0。图上 p_x \to p_y 的最短路就是答案。

但是现在有 m 组询问。对每个起点都跑一遍最短路显然不现实。观察到 n, m 同阶，且 a_i 值域较小（a_i \le V = 26^2），可以考虑 meet-in-the-middle 的思想。

我们发现，p_x \to p_y 要么是只通过相邻位置走过去（此时步数为 |x - y|），要么必须经过至少一个 q_i。考虑对于 \forall i \in [1, V], j \in [1, n]，预处理出 q_i \to p_j 的最短路 f_{i, j} 和 p_j \to q_i 的最短路 g_{i, j}，询问时我们枚举经过了哪个 q_i，答案就是 \min(|x - y|, \min\limits_{i = 1}^V g_{i, x} + f_{i, y} + 1)。

如果使用 01bfs 求最短路，时间复杂度就是 O(nV)。

code