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

标签: lca, construction

已有 2 条评论

  1. 已阅。

  2. orzfr orzfr

    orzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfr

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu