跳跳棋——二分+建模LCA

题目描述

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。

我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）

跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。

写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

思路

考虑一种类似于二叉树的结构，三个跳棋无法再跳的时候（即$|XY|=|YZ|$时），我把将它视为根，我们把初末状态视为$a,b$两个节点，那么其实就是找$a,b的LCA$，我们先找到$a,b$的根，如果根不同，没有解，否则我们先把$a,b$提到同一深度，记深度差为$x$，然后二分往上跳的高度，记为$l$，答案就是$x+l*2$

code

#include<bits/stdc++.h>

#define I inline

#define dist(x,y) (abs(x-y))

using namespace std;

const int inf=1e9+;

struct node

{

    int x[];

    int dep;

}a,b;

int depth;

int ans;

bool operator == (node a,node b)

{

    sort(a.x+,a.x+);sort(b.x+,b.x+);

    for(int i=;i<=;i++)if(a.x[i]!=b.x[i])return ;

    return ;

}

I node calc(node a,int k)

{

    int x=a.x[],y=a.x[],z=a.x[];

    node res;

    for(int i=;i<=;i++)res.x[i]=a.x[i];

    int d1=dist(x,y),d2=dist(y,z);

    if(d1==d2)return res;

    if(d1<d2)

    {

        int t=min(k,(d2-)/d1);

        x+=d1*t;y+=d1*t;

        k-=t;depth+=t;

    }

    else

    {

        int t=min(k,(d1-)/d2);

        y-=d2*t;z-=d2*t;

        k-=t;depth+=t;

    }

    res.x[]=x;res.x[]=y;res.x[]=z;

    if(k)return calc(res,k);

    return res;

}

int main()

{

    cin>>a.x[]>>a.x[]>>a.x[]>>b.x[]>>b.x[]>>b.x[];

    sort(a.x+,a.x+);sort(b.x+,b.x+);

    node rt1=calc(a,inf);a.dep=depth;depth=;

    node rt2=calc(b,inf);b.dep=depth;depth=;

    if(!(rt1==rt2)){cout<<"NO";return ;}

    if(a.dep<b.dep)swap(a,b);

    ans=a.dep-b.dep;

    a=calc(a,ans);

    int l=,r=b.dep;

    while(l<r-)

    {

        int mid=l+r>>;

        if(calc(a,mid)==calc(b,mid))r=mid;

        else l=mid;

    }

    while(!(calc(a,l)==calc(b,l)))l++;

    puts("YES");

    cout<<ans+l*;

}