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;
}
已阅。
orzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfrorzfr