[BZOJ 2144]跳跳棋

Description

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

Input

第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）第二行包含三个整数，表示目标位置x y z。（互不相同）

Output

如果无解，输出一行NO。如果可以到达，第一行输出YES，第二行输出最少步数。

Sample Input

1 2 3
0 3 5

Sample Output

YES
2

HINT

【范围】
100% 绝对值不超过10^9

题解

设初始状态为$sta$，目标状态为$fin$。我们先拿出初始状态三个球讨论。

由于三个球其实是相同的，则他们的相互顺序是不影响的，我们可以先按坐标从左至右排序为$a$,$b$,$c$。

平面上有三个球，我们来讨论它们跳的不同情况。

设：$p=b-a$,$q=c-b$

那么$b$可以跳动到$a$左边，或者$c$右边。

同时，如果$p<q$，那么$a$可以跳到$bc$中间，如果$p>q$，那么$c$可以跳到$ab$中间。

也就是说，如果$p≠q$，那么一个状态有$3$种跳法，但如果$p=q$，那么只有$2$种跳法。

如果我们用图来表示状态之间的关系，就很容易发现，状态之间组成的联系实际上是二叉树组成的森林。

每一个$p=q$的状态都是一棵二叉树的根。

其余的每个状态，$a$或$c$往中间跳表示往父亲节点走一步，对于所有状态，中间节点往左右跳分别对应往左右孩子走一步。

原问题转换成了树上最短路问题。原问题就是：

1.$sta$和$fin$是否同根。

2.如果同根，求$sta$到$fin$的距离。

这两个问题都可以用$LCA$来解决。

如果$sta$和$fin$不存在$LCA$那么输出$NO$。

如果存在，那么计算$LCA(sta,fin)$到$sta$和$fin$分别的距离，相加即为答案。

我们可以通过辗转相除法直接计算$sta$和$fin$在二叉树中的深度。

我们用类似倍增的$LCA$的思想，先将两个节点跳到同一深度，

求$2$个深度相同的点的$LCA$，我们可以采用二分答案的方法。

对于二分答案：$LCA$到$sta$的距离$mid$，如果$sta$往上走$mid$和$fin$往上走$mid$到达的点相同，那么答案$≤mid$

否则答案$＞mid$

如此一来，我们得到了一个$O(log^2 D)$的算法，$D$为深度。

  1 #include<set>
  2 #include<map>
  3 #include<ctime>
  4 #include<cmath>
  5 #include<queue>
  6 #include<stack>
  7 #include<vector>
  8 #include<cstdio>
  9 #include<string>
 10 #include<cstring>
 11 #include<cstdlib>
 12 #include<iostream>
 13 #include<algorithm>
 14 #define LL long long
 15 #define Max(a,b) ((a)>(b) ? (a):(b))
 16 #define Min(a,b) ((a)<(b) ? (a):(b))
 17 using namespace std;
 18 
 19 int depth;
 20 struct node
 21 {
 22     int a,b,c;
 23     node (){}
 24     node (int _a,int _b,int _c) {a=_a;b=_b;c=_c;}
 25     void sort()
 26     {
 27   　　  if (b>c) swap(b,c);
 28  　　   if (a>b) swap(a,b);
 29    　　 if (b>c) swap(b,c);
 30     }
 31     bool operator == (const node &B)
 32     const{
 33    　　 return (a==B.a)&&(b==B.b)&&(c==B.c);
 34     }
 35     node get_root()
 36     {
 37   　　  int dep=0;
 38   　　  node tmp=node(a,b,c);
 39  　　   int p=tmp.b-tmp.a,q=tmp.c-tmp.b;
 40    　　 while (p!=q)
 41   　　  {
 42     　　    int r;
 43       　　  if (p>q) r=(p-1)/q,tmp.b-=r*q,tmp.c-=r*q;
 44         　　else if (p<q) r=(q-1)/p,tmp.a+=r*p,tmp.b+=r*p;
 45        　　 p=tmp.b-tmp.a,q=tmp.c-tmp.b;
 46         　　dep+=r;
 47    　　 }
 48     　　depth=dep;
 49     　　return tmp;
 50     }
 51     node jump(int step)
 52     {
 53     　　node tmp=node(a,b,c);
 54   　　  int p=tmp.b-tmp.a,q=tmp.c-tmp.b;
 55     　　while (p!=q&&step)
 56     　　{
 57       　　  int r;
 58         　　if (p>q)
 59         　　{
 60        　　 　　r=(p-1)/q;
 61        　　　　 if (r>step) r=step;
 62        　　　　 tmp.b-=r*q,tmp.c-=r*q;
 63        　　 }
 64       　　  else if (p<q)
 65      　　   {
 66        　　　　 r=(q-1)/p;
 67        　　　　 if (r>step) r=step;
 68         　　　　tmp.a+=r*p,tmp.b+=r*p;
 69         　　}
 70         　　p=tmp.b-tmp.a,q=tmp.c-tmp.b;
 71         　　step-=r;
 72     　　}
 73     　　return tmp;
 74     }
 75 }sta,fin;
 76 
 77 int main()
 78 {
 79     scanf("%d%d%d",&sta.a,&sta.b,&sta.c);
 80     scanf("%d%d%d",&fin.a,&fin.b,&fin.c);
 81     sta.sort();
 82     fin.sort();
 83     if (sta.get_root()==fin.get_root())
 84     {
 85   　　  printf("YES
");
 86  　　   int dep_sta,dep_fin;
 87    　　 sta.get_root();dep_sta=depth;
 88    　　 fin.get_root();dep_fin=depth;
 89    　　 if (dep_sta<dep_fin) swap(sta,fin),swap(dep_sta,dep_fin);
 90    　　 int len=dep_sta-dep_fin;
 91    　　 sta=sta.jump(len);
 92     　　dep_sta=dep_fin;
 93    　　 if (sta==fin) printf("%d
",len);
 94    　　 else
 95    　　 {
 96      　　   int l=1,r=dep_sta,ans=dep_sta;
 97        　　 while (l<=r)
 98        　　 {
 99        　　　　 int mid=(l+r)>>1;
100         　　　　if (sta.jump(mid)==fin.jump(mid)) ans=mid,r=mid-1;
101        　　　　 else l=mid+1;
102      　　   }
103       　　  printf("%d
",len+2*ans);
104    　　 }
105     }
106     else printf("NO
");
107     return 0;
108 }