[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$为深度。

 #include<set>

 #include<map>

 #include<ctime>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<vector>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define LL long long

 #define Max(a,b) ((a)>(b) ? (a):(b))

 #define Min(a,b) ((a)<(b) ? (a):(b))

 using namespace std;

 int depth;

 struct node

 {

     int a,b,c;

     node (){}

     node (int _a,int _b,int _c) {a=_a;b=_b;c=_c;}

     void sort()

     {

   　　  if (b>c) swap(b,c);

  　　   if (a>b) swap(a,b);

    　　 if (b>c) swap(b,c);

     }

     bool operator == (const node &B)

     const{

    　　 return (a==B.a)&&(b==B.b)&&(c==B.c);

     }

     node get_root()

     {

   　　  int dep=;

   　　  node tmp=node(a,b,c);

  　　   int p=tmp.b-tmp.a,q=tmp.c-tmp.b;

    　　 while (p!=q)

   　　  {

     　　    int r;

       　　  if (p>q) r=(p-)/q,tmp.b-=r*q,tmp.c-=r*q;

         　　else if (p<q) r=(q-)/p,tmp.a+=r*p,tmp.b+=r*p;

        　　 p=tmp.b-tmp.a,q=tmp.c-tmp.b;

         　　dep+=r;

    　　 }

     　　depth=dep;

     　　return tmp;

     }

     node jump(int step)

     {

     　　node tmp=node(a,b,c);

   　　  int p=tmp.b-tmp.a,q=tmp.c-tmp.b;

     　　while (p!=q&&step)

     　　{

       　　  int r;

         　　if (p>q)

         　　{

        　　 　　r=(p-)/q;

        　　　　 if (r>step) r=step;

        　　　　 tmp.b-=r*q,tmp.c-=r*q;

        　　 }

       　　  else if (p<q)

      　　   {

        　　　　 r=(q-)/p;

        　　　　 if (r>step) r=step;

         　　　　tmp.a+=r*p,tmp.b+=r*p;

         　　}

         　　p=tmp.b-tmp.a,q=tmp.c-tmp.b;

         　　step-=r;

     　　}

     　　return tmp;

     }

 }sta,fin;

 int main()

 {

     scanf("%d%d%d",&sta.a,&sta.b,&sta.c);

     scanf("%d%d%d",&fin.a,&fin.b,&fin.c);

     sta.sort();

     fin.sort();

     if (sta.get_root()==fin.get_root())

     {

   　　  printf("YES\n");

  　　   int dep_sta,dep_fin;

    　　 sta.get_root();dep_sta=depth;

    　　 fin.get_root();dep_fin=depth;

    　　 if (dep_sta<dep_fin) swap(sta,fin),swap(dep_sta,dep_fin);

    　　 int len=dep_sta-dep_fin;

    　　 sta=sta.jump(len);

     　　dep_sta=dep_fin;

    　　 if (sta==fin) printf("%d\n",len);

    　　 else

    　　 {

      　　   int l=,r=dep_sta,ans=dep_sta;

        　　 while (l<=r)

        　　 {

        　　　　 int mid=(l+r)>>;

         　　　　if (sta.jump(mid)==fin.jump(mid)) ans=mid,r=mid-;

        　　　　 else l=mid+;

      　　   }

       　　  printf("%d\n",len+*ans);

    　　 }

     }

     else printf("NO\n");

     return ;

 }

巴特西