前言 一年多前写的题解，因为当时水平不高所以学的比较细致，写的也很细致，只修改了部分不影响阅读的内容。 分析问题 对第二类问题的形式分析，发现题目给出的两类问题本质上都可以转化为以下形式再解决： 两人从城市 sss 为起点最多行驶长为 XXX 的距离，他们开车行驶的距离分别是多少？ 在这里，我们用 da(s,X)da(s,X)da(s,X) 与 db(s,X)db(s,X)db(s,X) 表示此时小 A 与小 B 行驶过的路程，以便以后续分析。 做了这样的转化后，两类问题本质如下： * 询问从每个城市 iii 开始 da(i,X0)db(i,X0)\Large \frac{da(i,X_0)}{db(i,X_0)}db(i,X0 )da(i,X0 ) 的最大值。 * 多次询问 da(s,X)da(s,X)da(s,X) 与 db(s,X)db(s,X)db(s,X) 的值。 所以我们解决本题的关键在于快速计算 da(s,X)da(s,X)da(s,X) 与 db(s,X)db(s,X)db(s,X) 的值。 预处理 我们通过对问题的分析，知道了两类问题的本质。现在摆在面前的问题有两个： 1. 小 A 和小 B 在城市 iii 时行驶到的下一座城市是什么。 2. 某组问题下，两人行驶的距离分别是多少。 要解决第二个问题，就绕不开第一个问题。所以我们首先需要预处理出两人在城市 iii 分别行驶的下一座城市是什么，这里记作 gaiga_igai 与 gbigb_igbi . 解决这个问题其实有一个力大砖飞的做法，我们开个 set 倒序处理问题，每次查找前驱和后继，但是这里介绍一个比较精妙的链表做法。 首先我们分析 ∣hi−hj∣|h_i-h_j|∣hi −hj ∣ 的性质，对于一个确定的 iii，实际上能成为它最小值的数只有两个：第一个小于等于 hih_ihi 的数与第一个大于等于 hih_ihi 的数。这里把他们分别设为前驱 preipre_iprei 与后继 nxtinxt_inxti 。 为了求出前驱 preipre_iprei 与后继 nxtinxt_inxti 。我们不妨将 hhh 升序排序，然后记 rnkirnk_irnki 表示第 iii 座城市的排名。 考虑求 gaiga_igai 与 gbigb_igbi 的过程，此时前驱和后继都可能成为 gbigb_igbi ，采用比较距离谁更小的方法进行判断。而对于 gaiga_igai 的求法就稍微复杂一点了，它的决策和 gbigb_igbi 的取值有关，所以采用分类讨论来进行求解： * 当 gbi=preigb_i = pre_igbi =prei 时，说明此时的候选点可以是后继 nxtinxt_inxti 或者 preipre_iprei 的前驱，需要进行比较判断。 * 当 gbi=nxtigb_i = nxt_igbi =nxti 时，说明此时的候选点可以是前驱 preipre_iprei 或者 nxtinxt_inxti 的后继，需要进行比较判断。 这样就大功告成了？其实不然，因为两人只能去往 iii 后面的城市 jjj，而刚刚的算法没有考虑到这个问题，这样就影响了答案的正确性。 这个问题其实很好解决。实际上我们需要的只是在计算第 iii 个城市的答案后把它的影响撤销掉，这样就可以消除对答案的影响，所以这里我们采用更为简单的双向链表的方式实现。 这个算法流程的时间复杂度为 O(n)O(n)O(n)。注意，因为我们这里排了序，所以我们求 iii 的答案时，链表上对应的位置实际上为 rnkirnk_irnki ，不要搞混了。 动态规划 现在需要求解 da(s,X)da(s,X)da(s,X) 与 db(s,X)db(s,X)db(s,X) 的值，这里我们考虑采用动态规划。 以 da(s,X)da(s,X)da(s,X) 的转移为例，我们设 dai,j,0/1da_{i,j,0/1}dai,j,0/1 表示从第 iii 座城市开始，行驶时间是 jjj 天，现在是小 A 还是小 B 在开车。我们设上一座城市为 kkk，转移如下： * dai,j,0=dak,j−1,1+∣hi−hk∣(j>1)da_{i,j,0} = da_{k,j-1,1}+|h_i-h_k|(j>1)dai,j,0 =dak,j−1,1 +∣hi −hk ∣(j>1)。这里表示此时小 B 和小 A 换班，然后加上城市的距离。 * dai,j,1=dak,j−1,0+∣hi+hk∣(j>1)da_{i,j,1} = da_{k,j-1,0}+|h_i+h_k|(j>1)dai,j,1 =dak,j−1,0 +∣hi +hk ∣(j>1)。这里表示此时小 A 和小 B 换班，然后加上城市的距离。 这个 dp 显然是 O(n2)O(n^2)O(n2) 量级的，而我们查询一组 (s,X)(s,X)(s,X) 的答案所花费的时间是 O(n)O(n)O(n) 的，这并不够优秀。 优化动态规划一般我们就只从两个方向入手：优化状态设计与加速状态转移。这里我们先分析加速状态转移的做法，可以考虑采纳矩阵加速法，但是由于上一个城市的量级为 O(n)O(n)O(n)，直接使用使得这个算法反而还更劣。笔者并没有想到对应的优化方法，有方法的读者可以提出。 既然优化转移不行，那我们就从优化状态设计的角度下功夫。首先发现这三维状态好像都不省不掉的，但是可以优化表达方式。 我们考虑第一维 iii 和第三维 kkk，发现好像都不太能简化，但是第二维 jjj 似乎可以。我们发现 jjj 的大小与行驶的路程的大小相关，所以我们可以考虑二进制拆分的思想计算答案。 把 jjj 改写为二进制位的形式，这样状态设计就变为了：现在行驶到了第 iii 座城市，行驶时间是 2j2^j2j 天，现在是小 A 还是小 B 在开车。 这样我们同时需要知道 2j2^j2j 天后所跳跃到的城市。同理我们也可以设 fi,j,kf_{i,j,k}fi,j,k 表示对应状态所跳跃到的城市。此时三个数组的转移稍有不同，需要分析 j=1j=1j=1 时 kkk 的取值，转移如下： * fi,j,k={fi,0,1−kj=1fi,fi,j−1,k,kj>1f_{i,j,k} = \begin{cases} f_{i,0, 1-k} &j=1 \\f_{i,f_{i,j-1,k},k} & j>1 \end{cases}fi,j,k ={fi,0,1−k fi,fi,j−1,k ,k j=1j>1 * dai,j,k={dai,0,k+dafi,0,k,0,1−kj=1dai,j−1,k+dafi,j−1,k,j−1,kj>1da_{i,j,k} = \begin{cases} da_{i,0, k}+da_{f_{i,0,k},0,1-k} &j=1 \\da_{i,j-1,k}+da_{f_{i,j-1,k},j-1,k}& j>1 \end{cases}dai,j,k ={dai,0,k +dafi,0,k ,0,1−k dai,j−1,k +dafi,j−1,k ,j−1,k j=1j>1 * dbi,j,k={dbi,0,k+dbfi,0,k,0,1−kj=1dbi,j−1,k+dbfi,j−1,k,j−1,kj>1db_{i,j,k} = \begin{cases} db_{i,0, k}+db_{f_{i,0,k},0,1-k} &j=1 \\db_{i,j-1,k}+db_{f_{i,j-1,k},j-1,k}& j>1 \end{cases}dbi,j,k ={dbi,0,k +dbfi,0,k ,0,1−k dbi,j−1,k +dbfi,j−1,k ,j−1,k j=1j>1 当 j=0j=0j=0 需要初始化，依据刚刚计算的 gai,gbiga_i,gb_igai ,gbi 处理，这部分代码如下。 实际上这就是倍增的过程，像这样利用二进制拆分来动态规划的方法我们称之为倍增优化 dp。 查询答案 查询答案就好办了。对于一组 (s,X)(s,X)(s,X)，我们从高到低枚举二进制位，在路程不超过 XXX 的情况下直接跳跃即可。具体实现可以采用一个结构体存储 da(s,X)da(s,X)da(s,X) 与 db(s,X)db(s,X)db(s,X) 的值，此时这里需要注意转移到第 000 位时开车的人。 这样我们单次处理一组 (s,X)(s,X)(s,X) 的答案的复杂度为 O(log⁡n)O(\log n)O(logn)。总体的时间复杂度就是 O((n+q)log⁡n)O((n+q)\log n)O((n+q)logn)。总而言之是个经典题。