[EGOI2024] Circle Passing / 传球游戏
Forgotten_freopen
·
·
题解
一道豪丸的思维题。
题目大意
给定一个有 2n 个点和 2n + m 条边的无向图（点的编号为 0 到 2n - 1），其中点 i 和点 (i+1)\bmod 2n 之间有一条边，此外还有 m 条特殊边，第 i 条特殊边连接 k_i 和 k_i + n（1 \leq k_i \leq n）。
## 解析
$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)$。
```cpp
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
已经没什么好说的了，~~毕竟证明依托答辩。~~ 贴个代码吧。
（因为本人马蜂过于丑陋，在此只贴关键代码。）
```cpp
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后写的第一篇题解，希望能帮助到大家！如果有疏漏或错误欢迎指出！