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;
}