题解 P1852 【跳跳棋】

· · 题解

不得不说，这题建模极为抽象了，出题人太神了。看了好多篇题解才懂，自己也写一篇比较详细的吧

相信大家都玩过跳棋，有一个规则想必大家都知道，就是一次跳跃不能跳过两颗棋子

这个限制是解决这题的关键，有了这个限制，可以看出，对于两边的棋子，只能跳到其余两颗的中间，同样的中间的棋子也只能跳到两边

为了方便，我们将三个棋子标号，分别为x,y,z，且x<y<z。

移动棋子无非就四种讨论

因为有了不能一次跳过两颗棋的限制，所以第三种情况和第四种情况必然起了冲突

不妨设d1=y-x,d2=z-y，易得

也就是说我们对于每种状态只有三种转移方式

我们再看看这三个式子，可以发现，对于第一种和第二种情况，我们将中间的点向两边跳，相当于扩大了边界。而第三种两边向里面跳则恰恰相反，是将边界缩小了

是不是很像一棵二叉树？

现在可能还不够明显，我们再接下去推

有一个很显然的性质，边界不可能无限变小。也就是说缩着缩着会遇到一种情况不能再缩了，我们来思考一下什么情况不能再缩了

观察式子：

惊奇的发现，我们这样讨论漏了一种情况，d1=d2

这个非常好理解，如果d1=d2，那么x必然会与z跳到同一个点，而这是不符合题目描述的。所以当d1=d2时，这个状态只能由中间向两边跳，也就是只有两个转移状态，想想这个状态在二叉树中像什么？没错，根节点我们就这样找到了，二叉树的形态就像下图所示：

可以发现，对于每一组(x,y,z)都有唯一对应的一个根，而且二叉树之间的任意一组(x,y,z)都可以互相转化，而且转化的操作次数就等于两个状态在树上的距离

所以如果初始(x,y,z)的树根和目标(x',y',z')的树根不相同，那么就是No，因为无论怎么跳都出不去这棵树的范围，而根不同则说明树不同

所以对于初始(x,y,z)和目标(x',y',z')，我们只要求出它们的LCA，答案就是初始点到LCA的距离 + LCA到目标点的距离

不过因为范围太大，树无法存下，普通的LCA求法树剖、倍增等已经无法使用了

我们先不急着求LCA，来想想另一个问题

初始状态：(1,10,11)

目标状态：(1,2,3)

人脑模拟一下程序，d1>d2，转换成(1,9,10)，(d1>d2)，转换成(1,8,9)，d1>d2，转换成(1,7,8),\cdots\cdots

如果改成(1,inf-1,inf)呢？

显然要T飞

不过我们发现，一直在重复一个操作，所以可以将这些操作压缩

我们只讨论d1>d2的情况，d1<d2其实差不多

易发现，要连续跳(d1-1)/d2次同样的操作（每一次跳d2的距离，但又不能超越或跳到x，也就是总距离为(d1-1)，总次数故为(d1-1)/d2）

设：d3=(d1-1)/d2

所以最后是\large(x,y-d3\cdot d1,z-d3\cdot d1)

这样我们就大大的压缩了路径，但这样又有什么用呢？我们回到树上来

因为路径被压缩了，所以我们可以换种方法求LCA

方便起见，我们先将初始状态跳到和目标状态在树中的高度一致（如果目标状态高度更高我们就换一下，在树中的距离是没有方向的）

也是初始状态要向上跳Dep_T-Dep_S次（Dep表示深度，S和T分别表示起始状态和目标状态），而跳跃的操作我们就可以用压缩路径快速实现

好了，现在两个状态高度相同了

有个显然的性质，如果两个状态同时向上跳x次所跳到的节点相同，那么同时向上跳x+1次所跳到的节点也相同，也就是说明满足单调性。所以我们可以用二分来枚举最小的x满足了两个状态同时向上跳x次所跳到的节点相同，所以LCA就是两个同时向上跳x次所跳到的节点

然后就愉快的AC了

码量小但细节是真的多，思维难度也很好，总而言之就是一道质量非常高的建模LCA+二分的题目

如果有哪步我打错了，或者有一些没有理解的地方，欢迎私信或留言！

参考代码：

#include<bits/stdc++.h>
using namespace std;
int Cnt,Ans,d1,d2,d3,x,y,z,L,R,X,Y,Z,tot,a[5];
struct lc{
    int x,y,z,tot;
}A,B;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void Dfs(int x,int y,int z){
    tot=0;
    while (1){
        d1=y-x,d2=z-y;
        if (d1==d2) break;
        if (d1>d2) d3=(d1-1)/d2,tot+=d3,y-=d3*d2,z-=d3*d2;
        else d3=(d2-1)/d1,tot+=d3,x+=d3*d1,y+=d3*d1;
    }
    if (A.x||A.y) B=(lc){x,y,z,tot};
    else A=(lc){x,y,z,tot};
}
inline void Swap(){
    swap(x,X),swap(y,Y),swap(z,Z);
    swap(A.x,B.x),swap(A.y,B.y),swap(A.z,B.z),swap(A.tot,B.tot);
}
inline bool check(int T,int x,int y,int z,int X,int Y,int Z){
    tot=T;
    while (tot){
        d1=y-x,d2=z-y;
        if (d1==d2) break;
        if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,y-=d3*d2,z-=d3*d2;
        else d3=min((d2-1)/d1,tot),tot-=d3,x+=d3*d1,y+=d3*d1;
    }
    tot=T;
    while (tot){
        d1=Y-X,d2=Z-Y;
        if (d1==d2) break;
        if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,Y-=d3*d2,Z-=d3*d2;
        else d3=min((d2-1)/d1,tot),tot-=d3,X+=d3*d1,Y+=d3*d1;
    }
    return X==x&&Y==y&&Z==z;
}
int main(){
    for (int i=1;i<=3;i++) a[i]=read();
    sort(a+1,a+4);x=a[1],y=a[2],z=a[3];
    for (int i=1;i<=3;i++) a[i]=read();
    sort(a+1,a+4);X=a[1],Y=a[2],Z=a[3];
    Dfs(x,y,z);Dfs(X,Y,Z);
    if (A.x!=B.x||A.y!=B.y||A.z!=B.z){printf("NO");return 0;}
    if (A.tot<B.tot) Swap();
    Ans=tot=A.tot-B.tot;
    while (tot){
        d1=y-x,d2=z-y;
        if (d1==d2) break;
        if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,y-=d3*d2,z-=d3*d2;
        else d3=min((d2-1)/d1,tot),tot-=d3,x+=d3*d1,y+=d3*d1;
    }
    L=0,R=B.tot;
    while (L<=R){ 
        int mid=L+R>>1;
        if (check(mid,x,y,z,X,Y,Z)) Cnt=mid,R=mid-1;
        else L=mid+1;
    }
    printf("YES\n%d",Ans+Cnt*2);
    return 0;
}