LCA+二分

题目链接： HDU 3830 Checkers

题意：给定3个点$a,b,c$,每次操作可以跳到相邻点的对称位置。询问最终能否跳到$x,y,z$(不考虑顺序) 如果能，输出最小步数.

我们不妨设 $a<b<c$ , $b$可以跳到$2a-b$,$2c-b$,也即是往两边跳。
$a$和$c$可以往中间跳，我们可以发现如果$b-a==c-b$的时候我们就不能往中间跳了。
我们可以这样想，把$a,b,c$这三个的位置当成一个状态，而这个状态是二叉树中的一个节点，a和c往里跳相当于往父节点走，当$b-a==c-b$时说明走到了根节点。$b$往外跳相当去往子节点走，并且无穷无尽。

我们开始让$a$和$c$不断往里走，即不断往上寻找父节点，直至找到根节点。$a,b,c$和$x,y,z$具有相同根节点时，答案有解，此时答案树上两点的最短距离。也即是可以转化寻找LCA。往上走的时候不能一步一步走，比如三个数$1,2,101$，我们不能一步步翻$(2,3,101)$, $(3,4,101)$，这样太慢了，能不能直接翻到$(99,100,101)$。

首先要找到$a,b,c$和$x,y,z$走到根节点所需步数，也即是深度，然后将其中深度大的减小至共同深度。设深度差$dis$.二分答案，假设二分值为$mid$,如果它们俩往上走$mid$步就能处于共同坐标，那么可以$r=mid$,缩小答案，继续二分。二分结束的 $l$ 即是它们俩其中一个走向LCA所需步数。最终 $2 * l+dis$ 即为答案。

另外题目有多组输入，也没看到题目有说。

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<bitset>
#include<cmath>
using namespace std;
const int N = 1e6 + 100;
typedef long long ll;
struct state{
    ll a, b, c, cnt;//cnt表示当前状态走到根节点需要的步数
    bool operator == (const state &o)const{
        return a == o.a&&b == o.b&&c == o.c;
    }
};
state st, ed;
void Sort(state &cur)
{
    if (cur.a > cur.b)swap(cur.a, cur.b);
    if (cur.a > cur.c) swap(cur.a, cur.c);
    if (cur.b > cur.c) swap(cur.b, cur.c);
}
state getRoot(state cur)
{
    cur.cnt = 0;
    ll d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    while (d1 != d2)
    {
        ll t = 0;
        if (d1 > d2)
        {
            t = (d1 - 1) / d2;
            cur.b -= t*d2;
            cur.c -= t*d2;
        }
        else
        {
            t = (d2 - 1) / d1;
            cur.b += t*d1;
            cur.a += t*d1;
        }
        cur.cnt += t;
        Sort(cur);
        d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    }
    return cur;
}
state solve(state cur, ll dis)
{
    ll d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    while (dis&&d1!=d2)
    {
        ll t = 0;
        if (d1 > d2)
        {
            t = min((d1 - 1) / d2, dis);
            cur.b -= t*d2;
            cur.c -= t*d2;
        }
        else
        {
            t = min((d2 - 1) / d1, dis);
            cur.b += t*d1;
            cur.a += t*d1;
        }
        dis -= t;
        Sort(cur);
        d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    }
    return cur;
}
int main()
{
    while (scanf("%lld%lld%lld", &st.a, &st.b, &st.c) != EOF)
    {
        scanf("%lld%lld%lld", &ed.a, &ed.b, &ed.c);
        st.cnt = 0, ed.cnt = 0;
        Sort(st);
        Sort(ed);
        state st1 = getRoot(st), ed1 = getRoot(ed);//首先找到根节点
        st.cnt = st1.cnt, ed.cnt = ed1.cnt;//所需步数
        if (st1 == ed1){
            puts("YES");
            ll dis = abs(st.cnt - ed.cnt);
            if (st.cnt > ed.cnt){//提至同一深度
                st = solve(st, dis);
            }
            else{
                ed = solve(ed, dis);
            }
            ll l = 0, r = min(st.cnt, ed.cnt);
            while (l < r)
            {
                ll mid = (l + r) >> (1LL);
                state ss = solve(st, mid);
                state ee = solve(ed, mid);
                if (ss == ee) r = mid;
                else l = mid + 1;
            }
            printf("%lld\n", 2 * l + dis);
        }
        else{
            puts("NO");
        }
    }

    return 0;
}