跳跳棋（国家集训队，LCA，洛谷P1852，BZOJ[2144]）

题目

题目链接
描述
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有$3$3颗棋子，分别在$a，b，c$a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成$x，y，z$x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动两颗棋子距离不变。一次只允许跳过$1$1颗棋子。

写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
输入
第一行包含三个整数，表示当前棋子的位置$a b c$abc。（互不相同）
第二行包含三个整数，表示目标位置$x y z$xyz。（互不相同）
输出
如果无解，输出一行NO。如果可以到达，第一行输出YES，第二行输出最少步数。
样例输入
1 2 3
0 3 5
样例输出
YES
2
范围
$100\%$100% 绝对值不超过$10^9$109

思路

设有a，b，c三点，且$a\leq b \leq c$a≤b≤c
则有两种方式跳
一、b跳
则只有两种状态$（2a-b，a，c）$（2a−b，a，c）和$（a，c，2c-b）$（a，c，2c−b），可看做无限扩展
二、a，c绕着b跳，则有一下三种情况：
我们设$d_1 = b-a，d_2 = c-b$d1​=b−a，d2​=c−b。
1、$d_1 > d_2$d1​>d2​，即$c$c绕$b$b跳，也可理解为$b$b和$c$c向左平移$d_2$d2​个单位
2、$d_1 &lt; d_2$d1​<d2​，即$a$a绕$b$b跳，也可理解为$a$a和$b$b向右平移$d_1$d1​个单位
3、$d_1 = d_2$d1​=d2​，即无法再绕$b$b跳
如果一直按第二种方式跳，我们可以发现一定会得到$d_1=d_2$d1​=d2​的状态，之后就不能再按第二种方式跳了，所以我们可以把此时的状态当作根

所以我们把某一状态按第一种方式跳之后的状态当做子节点，按第二种方式跳之后的状态作为父亲（这里还用不到求LCA）

我们把$d_1=d_2$d1​=d2​的状态看做根，所以说当前状态到根的步数其实就是当前状态的深度
注意，我可没说要把状态储存起来

跳的优化：
有这样一个状态

如果你一步一步的跳，也许就会耗费时间。而我们可以知道，$d_1 = k*d_2+q(q&lt;d_1)$d1​=k∗d2​+q(q<d1​)，我们就可以把$b$b和$c$c都向左平移$k*d_2$k∗d2​个单位，因为题目说了，三个棋子是完全相同的，所以不用去细分次序。而$a，b$a，b的距离就是$q$q了

此题其实可以分为两个问题：

1. 如何判断有无解
   其实很好搞，只要我们一直按第二种方式跳，如果它们跳到不能再跳（到了根节点），判断根节点相不相同就行了（你莫给老子说不同子树下还有路径相连，你有毒吧）
2. 如何搞到最小步数
   这里才是LCA最大的用处。
   我们知道LCA有两种思想：
   1、先把两个点弄到同一深度，再一起爬山(暴力)
   2、tarjan
   在之前判断同一子树的时候我们就可以把深度处理出来，然后再把它们搞到同一深度，在二分枚举它们到LCA的深度，再看是否一样就行了

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int a[4];

    inline void sor_t(){
        sort(a+1, a+1+3);
        return;
    }

}fir, goal;

int dep1, dep2, cnt, ans;

bool flag;

inline int dfs(node x, int &dep){
    int d1 = x.a[2] - x.a[1];
    int d2 = x.a[3] - x.a[2];
    while( d1 != d2 ){
        if( d1 >= d2 ){
            int s_step = d1/d2, yu = d1%d2;
            if( !yu ){
                dep += s_step-1;
                return x.a[1];
            }
            d1 = yu, x.a[3] -= s_step*d2;
            dep += s_step, x.a[2] -= s_step*d2;
        }
        else{
            int s_step = d2/d1, yu = d2%d1;
            if( !yu ){
                dep += s_step-1;
                x.a[1] += (s_step-1)*d1;
                return x.a[1];
            }
            d2 = yu, x.a[1] += s_step*d1;
            dep += s_step, x.a[2] += s_step*d1;
        }
    }
    dep = 0;
    return x.a[1];
}

inline void check(int &x, int &y, int &z, int lim){
    int d1 = y-x, d2 = z-y;
    while( lim ){
        if( d1 > d2 ){
            int s_step = d1/d2, yu = d1%d2;
            if( s_step >= lim ){
                y -= lim*d2;
                z -= lim*d2;
                if( x == y ){
                    y = z;
                    z = y+d2;
                }
                return;
            }
            d1 = yu, lim-=s_step;
            y = x + yu, z = y + d2;
        }
        else{
            int s_step = d2/d1, yu = d2%d1;
            if( s_step >= lim ){
                x += lim*d1, y += lim*d1;
                if( y == z ){
                    y = x;
                    x = y-d1;
                }
                return;
            }
            d2 = yu, lim -= s_step;
            y = z - yu, x = y - d1;
        }
    }
}

int main(){
    for(int i = 1; i < 4; i ++)
        scanf("%d", &fir.a[i]);
    for(int i = 1; i < 4; i ++)
        scanf("%d", &goal.a[i]);
    fir.sor_t(), goal.sor_t();
    if(dfs(fir, dep1) != dfs(goal, dep2))
        printf("NO\n");
    else{
        puts("YES");
        if( dep1 > dep2 ){
            cnt = dep1 - dep2;
            check(fir.a[1], fir.a[2], fir.a[3], cnt);
        }
        else if( dep2 > dep1 ){
            cnt = dep2 - dep1;
            check(goal.a[1], goal.a[2], goal.a[3], cnt);
        }
        int l = 0, r = min(dep1, dep2);
        int ab[3] = {};
        int bc[3] = {};
        while( l <= r ){
            int mid = (l+r) >> 1;
            check(ab[0]=fir.a[1], ab[1]=fir.a[2], ab[2]=fir.a[3], mid);
            check(bc[0]=goal.a[1], bc[1]=goal.a[2], bc[2]=goal.a[3], mid);
            if( ab[0] == bc[0] && ab[1] == bc[1] && ab[2] == bc[2] ){
                ans = 2*mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        printf("%d\n", cnt + ans);
    }
    return 0;
}