P1852 跳跳棋

一个粗略的想法是对于所有状态 \((a,b,c)\) 之间连边，求出图之后跑最短路。

首先钦定 \(a\le b\le c\), 考虑转移有哪些情况：要么从两边到中间距离小的一个往中间跳缩小范围，要么中间往两边跳扩大范围。我们定义第一种到的状态为父亲，第二种到的状态为左右儿子，不难发现整个图是一棵二叉树森林。跳的过程和欧几里得算法十分类似，跳的次数实际不是很大。

于是我们直接暴力跳到根，判断是否在一棵树中，深度是好求的。LCA我们可以跳到同一高度之后二分/倍增得到。

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
	return s * f;
}

struct node {
	int x, y, z;
	inline node() { }
	inline node(int X, int Y, int Z) : x(X), y(Y), z(Z) { }
	inline void init() {
		if (x > y) swap(x, y);
		if (x > z) swap(x, z);
		if (y > z) swap(y, z);
	}
};

inline bool operator == (node a, node b) {
	return a.x == b.x && a.y == b.y && a.z == b.z;
}

inline pair<node, int> jump(node x, int k) {
	int p = k;
	while (k) {
		int n = x.y - x.x, m = x.z - x.y;
		if (n == m) return make_pair(x, p - k);
		if (n < m) {
			int d = min(k, (m - 1) / n);
			x.x += d * n; x.y += d * n;
			k -= d;
		} else {
			int d = min(k, (n - 1) / m);
			x.y -= d * m; x.z -= d * m;
			k -= d;
		}
	} return make_pair(x, p - k);
}

signed main() {
	node a, b;
	a.x = read(); a.y = read(); a.z = read(); a.init();
	b.x = read(); b.y = read(); b.z = read(); b.init();
	node ta, tb; int da, db;
	tie(ta, da) = jump(a, 1e9); tie(tb, db) = jump(b, 1e9);
	if (!(ta == tb)) { puts("NO"); return 0; }
	if (da < db) { swap(da, db); swap(a, b); }
	a = jump(a, da - db).first;
	if (a == b) { puts("YES"); printf("%lld\n", da - db); return 0; }
	for (int i = 30; ~i; --i) {
		if (!(jump(a, (1 << i)).first == jump(b, 1 << i).first)) {
			a = jump(a, (1 << i)).first;
			b = jump(b, (1 << i)).first;
		}
	} if (!(a == b)) a = jump(a, 1).first;
	int d; tie(a, d) = jump(a, 1e9);
	puts("YES"); printf("%lld\n", da + db - 2 * d);
	return 0;
}