自动搬运

查看原文

来自洛谷，原作者为

	ImposterAnYu I love barbara forever! | q3572195459 wx rzbxs3288，要电话请私信

搬运于2025-08-24 23:01:50，当前版本为作者最后更新于2024-08-06 12:00:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道豪丸的思维题。

题目大意

给定一个有 $2n$ 个点和 $2n + m$ 条边的无向图（点的编号为 $0$ 到 $2n - 1$），其中点 $i$ 和点 $(i+1)\bmod 2n$ 之间有一条边，此外还有 $m$ 条特殊边，第 $i$ 条特殊边连接 $k_i$ 和 $k_i + n$（$1 \leq k_i \leq n$）。

$q$ 组询问，每次询问给出一对点，求两点间的最短路。

解析

$1 \leq n \leq 5 \times 10^8$，显然无法直接建图，即使建图也无法快速求出两点间的最短路。

不过此题的边比较有特色：前 $2n$ 条边组成一个环，剩下的 $m$ 条边刚好连接一组最远点对（下文称该类边为对边）。所以，我们可以从特殊情况来考虑，即无对边时怎么做。

对于一对点 $x,y$，在没有对边的情况下，我们有两种走法：一种是经过 $x+1,x+2,...,y-1$，最后到 $y$，代价为 $\vert x - y\vert$；一种是先往 $0$ 走，绕到 $y$ 处，代价为 $2n - \vert x - y\vert$。因为这两种走法的路径加在一起就是走一整圈的长度，即 $2n$。

所以，在没有对边的情况下，$x,y$ 之间的距离即为 $\min(\vert x - y\vert,2n - \vert x - y\vert)$。

int1 dis(int1 x,int1 y){
	return min(abs(x - y),n2 - abs(x - y));
}

（代码中的 int1 就是本题用到的数据类型，在此题中为 int）

接下来考虑有对边的情况。

首先，假设 $y$ 在 $x$ 的对点的左侧（如左下图所示，如果在右侧的话可以通过交换 $x,y$ 使得 $y$ 在 $x$ 对点的左侧），且两端点同在 $x,y$ 所连边一侧（包括端点与 $x,y$ 重合的边）的对边为蓝边，两端点分别在 $x,y$ 所连边异侧的对边为红边（如右下图所示）。

图丑勿喷qwq

结论1：走任意蓝边所产生的最终代价相同。

往蓝边走（但不走蓝边）时代价相同，又因为蓝边在两点所连边的同侧，其能节省的代价自然也相同。证明跟证明了一样。

结论2：能走蓝边一定不走红边。

画图可以发现，走红边虽然同样可以可以直接穿行到对面，但两端点距离起点和终点的距离和相比蓝边较远，显然蓝边更优。

其实这两个结论都可以由画图可知，至于证明我不会。

得到这两个结论之后，考虑到每条边边权均为 $1$，我们可以得到一种贪心的做法：找到端点离起点最近的左侧边和右侧边，其中必然有一条红边。如果另一条为蓝边则走蓝边，答案只会更小；如果另一条边为红边，则和左侧的红边比较哪边更优——就用刚才的 $dis$ 函数。

至于如何判断另一条边是不是蓝边……其实没必要，找到这两条遍之后计算答案，取最优值即可（反正蓝边比红边更优）。不过由于靠起点近的边不一定靠终点近，所以对于起点和终点分别做一次同样的操作即可。

至于为什么只要找到离起点最近的左右各一条边……这就要涉及到我们的第三个结论了：

结论3：如果右侧最近的是红边，那么该红边的右侧一定不会存在蓝边。

这个终于可以给出证明了。

当右侧最近的为红边时，该红边的另一端点已经在左侧了（这一点由红边的定义可知），它右侧的边的另一端点只可能也在左侧。而根据蓝边的定义，右侧的蓝边的另一端点也在右侧，显然一个点不可能既在右侧又在左侧（当端点与终点重合时，右侧最近的也必然是蓝边，因为此时右侧最近的边的另一端点只会在右侧，假设不成立）。

最后一个问题：怎么找左侧和右侧最近的边？其实很好办，先将每条边的端点装入数组，对于每个 $x,y$，用二分查找（lower_bound）找到其右侧最近的边（包括端点与起点重合的边），这条边的前一条边就是其左侧最近的边。

但是考虑到原图（去掉特殊边）是个环，所以我们需要将边的端点复制一遍在数组后面。为了保证数组的单调性，同时也为了方便找到边的另一个端点，复制来的点的编号要加上 $2n$。

AC code

已经没什么好说的了，毕竟证明依托答辩。 贴个代码吧。

（因为本人马蜂过于丑陋，在此只贴关键代码。）

int1 dis(int1 x,int1 y){//求x，y间的距离。 
	return min(abs(x - y),n2 - abs(x - y));
}
int1 num(int1 x){//因为编号加过2n，要得到原先的编号需要取模 
	return (x - 1) % n2 + 1;
}
int1 solve(int1 x,int1 y){//起点为x，终点为y。 
	p = lower_bound(k + 1,k + m2 + 1,x) - k;
	if(p <= m2){
		a = k[p];//a为右侧最近的边（的最近端点） 
		s = dis(x,num(a)) + dis(num(a + n),y);//求走a所在边时的答案。a+n后再取模即为特殊边的另一端点。
	}else{
		s = INF;
	}
	if(p > 1){
		b = k[p - 1];//b为右侧最近的边（的最近端点） 
		t = dis(x,num(b)) + dis(num(b + n),y);//t的计算同s。
	}else{
		t = INF;
	}
	return min(dis(x,y),min(s,t) + 1);//为了严谨，在不走对边和走对边间取最小值。
}
int main(){
	n = read(),m = read(),q = read();
	for(i = 1,j = m + 1; i <= m; i++,j++){//k数组要开到4m！！！
		k[i] = read() + 1,k[j] = k[i] + n;//提前装入边的端点（因为题目给出的k已有单调性，所以不需排序）。 
	}//+1是个人习惯（因为不想处理0~2n-1就偏移成了1~2n） 
	n2 = n << 1,m2 = m << 1;//神奇的变量名。 
	for(i = 1,j = m2 + 1; i <= m2; i++,j++){
		k[j] = k[i] + n2;//为了方便处理右侧边端点编号较起点编号小的情况，将数组复制一份并加上2n。 
	}
	m2 <<= 1;
	while(q--){
		x = read() + 1,y = read() + 1;//这里+1也是个人习惯。 
		pe(min(solve(x,y),solve(y,x)));//对起点和终点同样处理一遍。 
	}
	return 0;
}

时间复杂度 $O(q \log m)$（瓶颈在于二分），空间复杂度为 $O(m)$。

回归OI后写的第一篇题解，希望能帮助到大家！如果有疏漏或错误欢迎指出！