jzoj 1917. 【2011集训队出题】跳跳棋 lca

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

Data Constraint

Hint

【数据范围】

　　20% 输入整数的绝对值均不超过10

　　40% 输入整数的绝对值均不超过10000

　　100% 绝对值不超过10^9

分析：根据题目意思，跳法有以下几种情况，

（1）中间的棋子向左跳

（2）中间的棋子向右跳

（3）因为只能越过一个棋子，设d1为最左棋子到中间棋子的距离，d2为中间棋子到右边棋子的距离，有

当d1 < <script type="math/tex" id="MathJax-Element-1"><</script>d2,左边的棋子跳到另外两个棋子中间。

当d1 > d2,右边的棋子跳到另外两个棋子中间。

当d1=d2,两边棋子无法运动。

我们可以把d1=d2看作终止状态。考虑从终止状态出发，它只有两种跳法（中间棋子向外跳）。当它跳到下一个状态时，该状态有三种状态，其中一种是跳回原来状态的，也就是说，为了步数最少，这种方案一定不行。剩下两种方案也是外跳……

如此看来，对于每个终止状态，可延伸的状态可以看作一棵二叉树，一开始的两个状态如果属于同一个终止状态（或者说同在以这个状态的树内），则有解，否则无解，最少步数应该为这两个状态在这棵树上的最短路。

这时，对于一个状态跳法(3)跳到的为父亲，外条为儿子，其实是求两个状态的lca。

对于状态(d1,d2,p),表示d1为最左棋子到中间棋子的距离，d2为中间棋子到右边棋子的距离，p为中间棋子的坐标，有

若d1<d2,父亲状态为(d1,d2-d1,p+d1)

若d1>d2,父亲状态为(d1-d2,d2,p-d2)

若d1=d2,则处于根状态。

我们发现，我们每次对于一个状态，d1 < <script type="math/tex" id="MathJax-Element-4"><</script>d2,下一个状态为(d1,d2-d1,p+d1)，若此时d1 < <script type="math/tex" id="MathJax-Element-5"><</script>d2-d1,下一个状态为(d1,d2-d1-d1,p+d1+d1),显然可以通过取mod直接使d1>d2,以此加速。

代码：

var
 x,y,z,a,b,c,dep1,dep2,i,ans,xx,yy,zz,a1,b1,c1,k,aa,bb,cc:longint;

function dfs(d1,d2,p:longint):longint;//表示查找一个状态的根状态，并记录该状态的深度
var g:longint;
 begin
  if d1=d2 then
   begin
    if xx<> then
     if (xx<>d1) or (yy<>d2) or (zz<>p) then
      begin
       writeln('NO');
       halt;
      end;
    xx:=d1; yy:=d2; zz:=p;
    exit();
   end;
  if d1<d2 then
   begin
    g:=d2 div d1;
    if d2 mod d1<> then exit(dfs(d1,d2-d1*g,p+d1*g)+g)
                    else exit(dfs(d1,d2-d1*(g-),p+d1*(g-))+g-);
   end
  else
   begin
    g:=d1 div d2;
    if d1 mod d2<> then exit(dfs(d1-d2*g,d2,p-d2*g)+g)
                    else exit(dfs(d1-d2*(g-),d2,p-d2*(g-))+g-);
   end;
 end;

function min(x,y:longint):longint;
 begin
  if x<y then exit(x)
         else exit(y);
 end;

procedure swap(var x,y:longint);
 begin
  x:=x xor y;
  y:=x xor y;
  x:=x xor y;
 end;

procedure sort(var x,y,z:longint);
 var t:longint;
begin
 if x>y then swap(x,y);
 if y>z then swap(y,z);
 if x>y then swap(x,y);
 end;

procedure up(var d1,d2,p:longint;dep:longint);//表示一个状态向上走dep步后的状态
 var i,g:longint;
begin
 i:=dep;
 while i> do
  begin
   if d1<d2 then
    begin
     g:=min(d2 div d1,i);
     d2:=d2-d1*g;
     p:=p+d1*g;
    end
   else
    begin
     g:=min(d1 div d2,i);
     d1:=d1-d2*g;
     p:=p-d2*g;
    end;
   i:=i-g;
  end;
end;

begin
 readln(a1,b1,c1);
 sort(a1,b1,c1);
 x:=b1-a1; y:=c1-b1; z:=b1;
 readln(a1,b1,c1);
 sort(a1,b1,c1);
 a:=b1-a1; b:=c1-b1; c:=b1;
 dep1:=dfs(x,y,z);
 dep2:=dfs(a,b,c);
 if dep1>dep2 then
  begin
   swap(x,a);
   swap(y,b);
   swap(z,c);
   swap(dep1,dep2);
  end;
 up(a,b,c,dep2-dep1);
 ans:=dep2-dep1;
 k:=;
 while k<dep1 do
  k:=k*;
 k:=k div ;
 while (k>) do
  begin
   if k<=dep1 then
    begin
     aa:=a; bb:=b; cc:=c;
     up(aa,bb,cc,k);
     xx:=x; yy:=y; zz:=z;
     up(xx,yy,zz,k);
     if (aa<>xx) or (bb<>yy) or (cc<>zz) then
      begin
       ans:=ans+*k;
       a:=aa; b:=bb; c:=cc;
       x:=xx; y:=yy; z:=zz;
       dep1:=dep1-k;
      end;
    end;
   k:=k div ;
  end;
 if (a<>x) and (b<>y) and (c<>z) then ans:=ans+; 
 writeln('YES');
 writeln(ans);
end.