BZOJ 2144 LCA

Prob.

给一个三元组描述数轴上的点。问通过跳棋规则能否得到给定状态。输出最小次数。
值 $ \le 10^9 $

Sol.

贼tm妙我跟你说。
对每个状态$ (x,y,z) $我们考虑能怎么变化：
1°中间往两边外跳，得到 $ (2x-y,x,z)(x,z,2z-y) $；
2°两边往中间跳，易知距离短的那一边才能跳，不妨设在左边，则得到$ (y,2y-x,z) $。
我们让2°作为当前状态的父亲，1°作为儿子，发现这是一棵树。注意两边距离相等则不能再以2°方式跳，此时为根。
求出根就可以判断在不在同一棵树上了。之后次数就是树上距离。

考虑如何快速计算树上距离。
令 $ u=y-x,v=z-y $，在一棵树上可用 $ (u,v) $ 唯一表示，则其父亲为 $ (u,v-u)$ 或 $(v,u-v) $。
这即欧几里得算法。
二分得出LCA。复杂度$ O(\lg n) $。

Code(820 kb 0 ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int INF = 1000000000;
struct Triple 
{
    int x, y, z; 
    Triple(int d = 0, int e = 0, int f = 0)
    {
        x = d, y = e, z = f;
        if(x > y) swap(x, y); if(y > z) swap(y, z); if(x > y) swap(x, y);
    }
    bool operator==(const Triple& r){return x == r.x && y == r.y && z == r.z;}
};
int len;
Triple getfa(Triple a, int h)
{
    len = 0;
    for(int k = 0; h; len += k)
    {
        int u = a.y - a.x, v = a.z - a.y;
        if(u == v) return a;
        if(u < v) 
        {
            k = min((v - 1) / u, h);
            a.x += k * u, a.y += k * u, h -= k;
        }
        else
        {
            k = min((u - 1) / v, h);
            a.y -= k * v, a.z -= k * v, h -= k;
        }
    }
    return a;
}
int main()
{
    int a, b, c; read(a, b, c);
    int x, y, z; read(x, y, z);
    Triple n = Triple(a, b, c), m = Triple(x, y, z);
    Triple s = getfa(n, INF); int h1 = len;
    Triple t = getfa(m, INF); int h2 = len;
    if(!(s == t)) {puts("NO"); return 0;}
    if(h1 < h2) swap(n, m), swap(h1, h2);
    n = getfa(n, h1 - h2);
    int L = 0, R = h2;
    while(L < R)
    {
        int M = (L + R) >> 1;
        if(getfa(n, M) == getfa(m, M)) R = M;
        else L = M + 1;
    }
    printf("YES\n%d\n", h1 - h2 + L * 2);
    return 0;
}