跳跳棋

原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=2144

题目描述

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

数据范围

100% 绝对值不超过109。

题解

首先说明一下，本人不太聪明，是一名蒟蒻，方法可能比较笨。

我们考虑一个有序状态 S( x ,y, z )，x<= y <=z。观察他的转移方案： 设 l =y- x ,r= z -y。 <1>中间向两边跳，( x ,y, z )–>(x- l ,y- l ,z)或( x ,y, z ) –> (x, y +r, z +r) <2>中间向两边跳， l < r，( x ,y, z ) –> (x+ l ,y+ l ,z) 或 l > r ，( x ,y, z ) –> (x, y -r, z -r)。

首先，有一个很显然 的性质，转移可逆。 我们将一个状态 两边向中间转移后 的状态设为这个状态的父亲，我们会惊奇的发现，这刚好构成了一棵树！！！ 然后问题就变成了询问两点间的距离。

有了上述结论，就简单多了。 首先，我们先让起始位置和目标位置跳到根上，但是如果一个一个的跳，很明显会超时。 其实我们发现，操作都是连续着跳（连续的一段跳动都是同一个方向的），例如说， l < r，我让它一次性跳完 ⌊rl⌋ 就好了，就跟更相减损术一样。终结条件是 l =r。时间复杂度是 log 级别。

判断起始位置的根是否和目标位置的根相同，如果是，则说明他们有交集，他们在同一棵树上，否则，则说明他们分别在两棵根不同的树上，无解。

在求根的时候顺便求出起始位置和初始位置的深度。 用上面 log 级别的跳动方法将两个点调节到深度一样的位置。 然后再用二分或倍增套用 log 级别跳法求出两个点的lca(最近公共祖先)，那我们就可以知道答案了。

Code(Pascal)

//本人比较蠢，打的代码很长，毕竟是蒟蒻嘛（仅供参考） label 123,999; var a,b,c,d,e,f:array[0..3] of longint; bo:boolean; n,m,j,k,l,i,o,p,ANS,p1,p2,pa,pb,tpa,tpb,dis,kkkk:longint; function js(a,b:longint):longint; begin if a>b then begin js:=a div b; if a mod b=0 then dec(js); end; if a<b then begin js:=b div a; if b mod a=0 then dec(js); end; end; PROCedure tiaoa(kkk:longint); begin if kkk=0 then exit; while pa>kkk do begin p1:=a[2]-a[1]; p2:=a[3]-a[2]; o:=js(p1,p2); if p1<p2 then begin if pa-o<=kkk then begin a[1]:=a[1]+(pa-kkk)*p1; a[2]:=a[2]+(pa-kkk)*p1; pa:=kkk; break; end; pa:=pa-o; a[1]:=a[1]+o*p1; a[2]:=a[2]+o*p1; end else if p2<p1 then begin if pa-o<=kkk then begin a[2]:=a[2]-(pa-kkk)*p2; a[3]:=a[3]-(pa-kkk)*p2; pa:=kkk; break; end; pa:=pa-o; a[2]:=a[2]-o*p2; a[3]:=a[3]-o*p2; end; end; end; PROCedure tiaob(kkk:longint); begin if kkk=0 then exit; while pb>kkk do begin p1:=b[2]-b[1]; p2:=b[3]-b[2]; o:=js(p1,p2); if p1<p2 then begin if pb-o<=kkk then begin b[1]:=b[1]+(pb-kkk)*p1; b[2]:=b[2]+(pb-kkk)*p1; pb:=kkk; break; end; pb:=pb-o; b[1]:=b[1]+o*p1; b[2]:=b[2]+o*p1; end else if p2<p1 then begin if pb-o<=pa then begin b[2]:=b[2]-(pb-kkk)*p2; b[3]:=b[3]-(pb-kkk)*p2; pb:=kkk; break; end; pb:=pb-o; b[2]:=b[2]-o*p2; b[3]:=b[3]-o*p2; end; end; end; begin readln(a[1],a[2],a[3]); readln(b[1],b[2],b[3]); for i:=1 to 2 do for l:=i+1 to 3 do if a[i]>a[l] then begin a[0]:=a[i]; a[i]:=a[l]; a[l]:=a[0]; end; for i:=1 to 2 do for l:=i+1 to 3 do if b[i]>b[l] then begin b[0]:=b[i]; b[i]:=b[l]; b[l]:=b[0]; end; c:=a; d:=b; pa:=0; while (c[1]+1<c[2]) or (c[2]+1<c[3]) do begin p1:=c[2]-c[1]; p2:=c[3]-c[2]; o:=js(p1,p2); if p1<p2 then begin pa:=pa+o; c[2]:=c[2]+p1*o; c[1]:=c[1]+p1*o; end else if p1>p2 then begin pa:=pa+o; c[3]:=c[3]-p2*o; c[2]:=c[2]-p2*o; end else break; end; e:=c; pb:=0; while (d[1]+1<d[2]) or (d[2]+1<d[3]) do begin p1:=d[2]-d[1]; p2:=d[3]-d[2]; o:=js(p1,p2); if p1<p2 then begin pb:=pb+o; d[2]:=d[2]+p1*o; d[1]:=d[1]+p1*o; end else if p1>p2 then begin pb:=pb+o; d[3]:=d[3]-p2*o; d[2]:=d[2]-p2*o; end else break; end; f:=d; if not((e[1]=f[1]) and (e[2]=f[2]) and (e[3]=f[3])) then begin 123: writeln('NO'); exit; end; if (pa=0) or (pb=0) then begin inc(pa); inc(pb); end; inc(pa); inc(pb); ans:=abs(pa-pb); TIAOA(pb); tiaob(pa); k:=trunc(ln(pa)/ln(2)); kkkk:=pa; while k>=0 do begin C:=A; D:=B; TPA:=pa; tpb:=pb; dis:=1 shl k; if tpa-dis<=1 then goto 999; tiaoa(tpa-dis); tiaob(tpb-dis); if (a[1]=b[1]) and (a[2]=b[2]) and (a[3]=b[3]) then begin pa:=tpa; pb:=tpb; a:=c; b:=d; end; 999:dec(k); end; if (not((a[1]=b[1]) and (a[2]=b[2]) and (a[3]=b[3]))) and (pa>=1) then dec(pa); ans:=ans+2*(kkkk-pa); writeln('YES'); writeln(ans); end.