[BZOJ2144]跳跳棋
试题描述
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。 
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。 输入
第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）第二行包含三个整数，表示目标位置x y z。（互不相同）
输出
如果无解，输出一行NO。如果可以到达，第一行输出YES，第二行输出最少步数。
输入示例
1 2 30 3 5
输出示例
YES2
数据规模及约定
100% 绝对值不超过10^9
题解
这是一道思路神题。
首先你要想到能够把状态转移放到一棵树里。具体做法是每种状态有两种往外跳的方案（中间的点向左或向右跳），或者只有一边的棋子能够跳到另外两个棋子中间（这种情况可能不存在，就是在三个数构成等差数列时），那么我们把两种往外跳的转移作为这个状态的两个儿子，往中间跳的转移作为父亲（不存在的话就是根）。
然后我们发现这棵树可能很长很大，比如
(a, b, c) = (0, 1, 1e9)
(x, y, z) = (1e9 - 2, 1e9 - 1, 1e9)
那么会有一条边数为 1e9 - 2 的链。
但是明显这条链有规律，就是每次移动都是左边两个数加上前两个数的差，那么我们就可以通过简单的除法跳到这条链的顶端；然后就可能轮到右边的两个数往左跳；这整个过程就是一个辗转相除的过程了。
然后我们对于两个状态，我们让它们往上跳到根（这个过程显然可以记录一下两个状态分别所在深度），如果根不相同就表明不存在方案；否则我们就可以像倍增求 lca 一样把两个状态调到同一深度，然后二分它们到 lca 的距离。
#include#include #include #include #include #include using namespace std;int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define oo 1000000000int dep;struct Sta { int A[3]; Sta() {} Sta(int _1, int _2, int _3) { A[0] = _1; A[1] = _2; A[2] = _3; sort(A, A + 3); } bool operator == (const Sta& t) const { return A[0] == t.A[0] && A[1] == t.A[1] && A[2] == t.A[2]; } bool operator != (const Sta& t) const { return !(*this == t); } Sta jump(int step) { Sta ans = *this; int l1 = ans.A[1] - ans.A[0], l2 = ans.A[2] - ans.A[1]; if(l1 == l2) return ans; if(l1 < l2) { int k = min(step, (l2 - 1) / l1); step -= k; dep += k; ans.A[0] += k * l1; ans.A[1] += k * l1; } else { int k = min(step, (l1 - 1) / l2); step -= k; dep += k; ans.A[1] -= k * l2; ans.A[2] -= k * l2; } if(step) return ans.jump(step); return ans; }} st, en;int main() { int a = read(), b = read(), c = read(); st = Sta(a, b, c); a = read(); b = read(); c = read(); en = Sta(a, b, c); Sta tmp1, tmp2; int h1, h2; dep = 0; tmp1 = st.jump(oo); h1 = dep; dep = 0; tmp2 = en.jump(oo); h2 = dep; if(tmp1 != tmp2) return puts("NO"), 0; puts("YES"); if(h1 < h2) swap(h1, h2), swap(st, en); st = st.jump(h1 - h2); int l = -1, r = oo + 1; while(r - l > 1) { int mid = l + r >> 1; if(st.jump(mid) == en.jump(mid)) r = mid; else l = mid; } printf("%d\n", (++l << 1) + h1 - h2); return 0;}