Luogu | P1852 跳跳棋 | LCA | 建模 / 二分答案
Description
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。
我们用跳跳棋来做一个简单的游戏：棋盘上有 $3$ 颗棋子，分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$ 。（棋子没有区别）
跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过 $1$ 颗棋子。
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
Input Format
第一行包含三个整数，表示当前棋子的位置$a,b,c$。（互不相同）
第二行包含三个整数，表示目标位置$x,y,z$。（互不相同）
Output Format
如果无解，输出一行
NO。如果可以到达，第一行输出
YES，第二行输出最少步数。
Input Sample
Sample 01
1 2 3
0 3 5
Output Sample
Sample 01
YES
2
Data Range
$|a,b,c,x,y,z| \le 10^9$。
Solution
考虑一个状态 $x,y,z$ （升序），则每次跳只有三种情况：
- $y$ 绕过 $x$ 向外跳。
- $y$ 绕过 $z$ 向外跳。
- $x$ 和 $z$ 离 $y$ 近的绕过 $y$ 向内跳。
那么可以将各个状态模拟成树上的点。前两种状态是指向儿子的边，最后一种状态是指向父亲的边。当距离相等时则不能向内跳，则意味着到了根节点。
显然一棵树上的点都可以相互转化。考虑将点向内跳，则相当于将两个距离较近的点都向内平移他们的距离。可以用除法加速跳的过程。
确定两个点是在同一棵树上后，二分猜到 LCA 的距离，验证即可。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)
using std::sort;
inline void Read(int &x){
x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}
int a[4];
int b[4];
int a_bk[4];
int b_bk[4];
int d1;
int d2;
void Find_root(int *a,int &d){
while(a[2]-a[1]!=a[3]-a[2]){
if(a[2]-a[1]<a[3]-a[2]){
int dlt=a[2]-a[1];
if((a[3]-a[2])%dlt){
int mtp=(a[3]-a[2])/dlt;
d+=mtp;
a[2]+=dlt*mtp;
a[1]+=dlt*mtp;
}
else{
int mtp=(a[3]-a[2])/dlt-1;
d+=mtp;
a[2]+=dlt*mtp;
a[1]+=dlt*mtp;
}
}
else{
int dlt=a[3]-a[2];
if((a[2]-a[1])%dlt){
int mtp=(a[2]-a[1])/dlt;
d+=mtp;
a[3]-=mtp*dlt;
a[2]-=mtp*dlt;
}
else{
int mtp=(a[2]-a[1])/dlt-1;
d+=mtp;
a[3]-=mtp*dlt;
a[2]-=mtp*dlt;
}
}
}
return;
}
void Climb(int *a,int fl){
int d=0;
while(a[2]-a[1]!=a[3]-a[2]){
if(a[2]-a[1]<a[3]-a[2]){
int dlt=a[2]-a[1];
if((a[3]-a[2])%dlt){
int mtp=(a[3]-a[2])/dlt;
if(d+mtp>=fl)
mtp=fl-d;
d+=mtp;
a[2]+=dlt*mtp;
a[1]+=dlt*mtp;
}
else{
int mtp=(a[3]-a[2])/dlt-1;
if(d+mtp>=fl)
mtp=fl-d;
d+=mtp;
a[2]+=dlt*mtp;
a[1]+=dlt*mtp;
}
}
else{
int dlt=a[3]-a[2];
if((a[2]-a[1])%dlt){
int mtp=(a[2]-a[1])/dlt;
if(d+mtp>=fl)
mtp=fl-d;
d+=mtp;
a[3]-=mtp*dlt;
a[2]-=mtp*dlt;
}
else{
int mtp=(a[2]-a[1])/dlt-1;
if(d+mtp>=fl)
mtp=fl-d;
d+=mtp;
a[3]-=mtp*dlt;
a[2]-=mtp*dlt;
}
}
if(d==fl)
return;
}
return;
}
void DoBackup(){
rep(i,1,3)
a_bk[i]=a[i],
b_bk[i]=b[i];
return;
}
void DoRecovery(){
rep(i,1,3)
a[i]=a_bk[i],
b[i]=b_bk[i];
return;
}
bool Check(){
rep(i,1,3)
if(a[i]!=b[i])
return false;
return true;
}
int main(){
rep(i,1,3)
scanf("%d",&a[i]);
rep(i,1,3)
scanf("%d",&b[i]);
sort(a+1,a+1+3);
sort(b+1,b+1+3);
DoBackup();
Find_root(a,d1);
Find_root(b,d2);
rep(i,1,3)
if(a[i]!=b[i])
return printf("NO\n"),0;
DoRecovery();
if(d1<d2){
rep(i,1,3)
swap(a[i],b[i]);
swap(d1,d2);
}
Climb(a,d1-d2);
DoBackup();
int dlt=d1-d2;
int L=0;
int R=d2;
int ans=0;
while(L<=R){
int mid=(L+R)>>1;
Climb(a,mid);
Climb(b,mid);
if(Check())
ans=2*mid,R=mid-1;
else
L=mid+1;
DoRecovery();
}
printf("YES\n%d\n",ans+dlt);
return 0;
}
