【神仙题目】【LCA】洛谷P1852 跳跳棋

Link

这题妙啊，

---

题目

---

解

由"一次只能跳过一颗棋子"，得到此题的一个重要性质：
这三个棋在某一时刻至多有3种跳法：中间的往左右跳，或离中间棋子较近的棋子跳往中间。像这样

而当AB=BC时只有两种跳法（A跳不到A’的位置）
当外面的点往里跳后，这三个棋子的范围会越来越小，直到出现不能往里跳的情况。
我们发现，此时的状态是唯一的：这三个棋子不可能在其它地方重现此时的相对状态。
我们就把这样的状态作为根；
判断两组棋子的根，如果它们不相同，说明它们永远不可能摆成另外一组的样子；直接输出No。
如果它们能摆成同一个根，那么我们就需要LCA（求最近公共祖先）了。
第一组棋子最终会先移动到LCA的状态再移到第二组棋子的状态。

注意

• 求LCA时我们用不了倍增，但可以用二分加速
• 万一AB很近而BC很远很远，这里可以优化一下，像这样：
  
  AB移动时直接加上 (k-1)*AB 就好了。（平移大法）由于棋子没有特别要区别，所以不用在意AB位置是否交换的问题。

---

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int astep,bstep;
struct asdf{
 int a,b,c;
} A,B,Fka,Fkb;
void px(asdf &LL){   //排序...
 if(LL.a>LL.b) swap(LL.a,LL.b);
 if(LL.a>LL.c) swap(LL.a,LL.c);
 if(LL.b>LL.c) swap(LL.b,LL.c);
}
int getroot(int &aa,int &bb,int &cc){  //找到根
 int step = 0,l,jl1,jl2;
 while(aa+cc!=bb*2){  //如果AB!=AC
  jl1 = bb-aa;//AB
  jl2 = cc-bb;//BC
  if(jl1<jl2){  //左边往里
   l = jl2/jl1;  //计算能跳几次
   if(jl2%jl1 == 0) --l;
   aa += jl1*l;  //平移
   bb += jl1*l;
   step += l;  //统计步数
  } 
  else {  //右边往里 //同上
   l = jl1/jl2;
   if(jl1%jl2 == 0) --l;
   bb -= jl2*l;
   cc -= jl2*l;
   step += l;
  }
 }
 return step;
}
asdf jummp(asdf ll,int step){  //ll状态上跳step步
 int l,jl1,jl2;
 while(step){ 
  jl1 = ll.b-ll.a;  //跟找根的方法相同，不想打注释了
  jl2 = ll.c-ll.b;
  if(jl1<jl2){
   l = jl2/jl1;
   if(jl2%jl1 == 0) --l;
   l = min(l,step);
   ll.a += jl1*l;
   ll.b += jl1*l;
   step -= l;
  } 
  else {
   l = jl1/jl2;
   if(jl1%jl2 == 0) --l;
   l = min(l,step);
   ll.b -= jl2*l;
   ll.c -= jl2*l;
   step -= l;
  }
 }
 return ll;
}
bool db(asdf aa,asdf bb){  //比较这两个状态是否相同
 if(aa.a!=bb.a||aa.b!=bb.b||aa.c!=bb.c) return 0;
 return 1;
}
int main(){
 scanf("%d%d%d%d%d%d",&A.a,&A.b,&A.c,&B.a,&B.b,&B.c);
 px(A); px(B);  //排序
 Fka = A;   //临时储存
 Fkb = B;
 astep = getroot(Fka.a,Fka.b,Fka.c);   //找根
 bstep = getroot(Fkb.a,Fkb.b,Fkb.c);
 if(db(Fka,Fkb)==0){  //根不同
  printf("NO");
  return 0;
 }
 if(astep > bstep) A = jummp(A,astep-bstep);  //先跳到同一高度
 else B = jummp(B,bstep-astep);
 int l = 0,r = min(astep,bstep), mid;  //二分
 while(l<r){
  mid = (l+r)/2;
  Fka = jummp(A,mid);
  Fkb = jummp(B,mid);
  if(db(Fka,Fkb) == 1) r = mid;  //跳mid*2步可以到达
  else l = mid+1;   //不行
 }
 printf("YES\n%d",max(astep-bstep,bstep-astep)+r*2);
}