2144: 跳跳棋

题目链接

题目大意：数轴上三个棋子，初始位置x,y,z。用最少操作次数变成a,b,c。每次操作选一个棋子，以另一棋子为中轴跳动，跳跃后距离不变，一次只能跳过一颗棋子

题解：观察发现，状态的转移形成了一张图，可以在图上跑最短路，正确性显然，但这样比较容易T（我没写）。再观察一下，发现若(x,y,z)往两边跳得到状态(u,v,w)，那么(x,y,z)是(u,v,w)往中间跳得到状态，也就是说，这个图实际上是树，向里跳是父结点，向外跳是儿子结点。树上距离显然可以用倍增lca来搞，但是由于状态不好存。如果可以迅速得到(logn)状态x向上k层的祖先，问题便迎刃而解。超级神的模拟gcd思想Orz 然后二分模拟倍增lca