题目传送门
【题目大意】
【思路分析】
这题预处理的部分有点多：
1.小A和小B从城市$i$出发，行驶到第下一个城市$ga[i]$和$gb[i]$
详细做法参见例题邻值查找
2.设$f[i][j][k]$表示从城市$j$出发，行驶了$2^i$天，$k$先开车，最终会到达的城市编号。$k$等于0或1，0表示轮到小A开车，1表示轮到小B开车。
初始值：$f[0][j][0]=ga[j],f[0][j][1]=gb[j]$
当$i=1$时，因为$2^0$是奇数，所以从$j$出发开车$2^1$天到达的城市，等于$k$先开$2^0$天，另一个人$1-k$再开$2^0$天到达的城市，即
$$f[1][j][k]=f[0][f[0][j][k]][1-k]$$
当$i>1$时，因为$2^{i-1}$是偶数，所以前后两段路都轮到$k$先开车，即
$$f[i][j][k]=f[i-1][f[i-1][j][k]][k]$$
具体实现时要注意$ga,gb,f$数组到达的城市超过第$N$个城市的边界的情况。
3.设$da[i][j][k]$表示在此状态下，小A行驶的路程总长度。
初始值：$da[0][j][0]=dist[j][ga[j]],da[0][j][1]=0$
当$i=1$时
$$da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k]$$
当$i>1$时
$$da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k]$$
$db[i][j][k]$也同理可得。
接下来才算进入正题，设$calc(S,X)$表示“从城市$S$出发最多行驶$X$公里”时，A和B分别行驶了多长的路程。
我们用倍增的思想来解决问题：
1.初始化当前城市$p=S$，小A、小B累计行驶路程$la=0,lb=0$
2.倒序循环$i=log_2N～0$
3.对于每个$i$，若两人从$p$出发行驶$2^i$天，累计路程仍未超过$X$，即$la+lb+da[i][p][0]+db[i][p][0]\le X$，则令$la=la+da[i][p][0],lb=lb+db[i][p][0],p=f[i][p][0]$
4.循环结束后，$la,lb$即为问题的答案
对于问题一，枚举起点$S_i$，取A、B行驶路程比值较小的$calc(S_i,X_0)$，即可求出问题一答案。
对于问题二，多次询问$calc(S_i,X_i)$，也可以直接计算。
整个算法的时间复杂度为$O((N+M)log_2N)$
【代码实现】
转载于:https://www.cnblogs.com/THWZF/p/11230154.html
