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.