BZOJ2144:跳跳棋 LCA

思路:

对于一个状态\((x,y,z)(x<y<z)\),我们发现可行的操作仅有三种:

(1)将\(y\)向左移动

(2)将\(y\)向右移动

(3)将\(x,z\)中离\(y\)比较近的一个以\(y\)为中心移动.(当\(y-x=z-y\)时不能这样做)

那么有人就要问了,还有离\(y\)比较远的以\(y\)为中心移动的情况呢?这必然与(1)(2)中的一个等价.

因此,我们可以将状态建成一棵树,对于一个状态,(1)(2)得到的是这个状态的左右儿子,(3)得到的是这个状态的父亲.

那么就很容易处理了.我们类似寻找LCA的过程不断向上爬即可.但我们不是暴力的向上找父亲,而是发现连续的若干次找父亲其实就是一个做gcd的过程.利用Euclid加速即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
struct Pos{
    int x,y,z;
    Pos(){}
    Pos(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
    bool operator!=(const Pos&B)const{return x!=B.x||y!=B.y||z!=B.z;}
    bool operator==(const Pos&B)const{return x==B.x&&y==B.y&&z==B.z;}
};
 
LL updep;
inline Pos up(int x,int y,int z,LL d){
    if(d==0)return Pos(x,y,z);
    if(y-x==z-y)return Pos(x,y,z);
    int d1=y-x,d2=z-y,step;
    if(d1>d2){
        if(d1%d2==0){
            step=d1/d2-1;
            if(d<=step)return updep+=d,Pos(x,x+d1-d*d2,x+d1-d*d2+d2);
            else return updep+=step,up(x,x+d2,x+2*d2,d-step);
        }
        else{
            step=d1/d2;
            if(d<=step)return updep+=d,Pos(x,x+d1-d*d2,x+d1-d*d2+d2);
            else return updep+=step,up(x,x+d1%d2,x+d1%d2+d2,d-step);
        }
    }
    else{
        if(d2%d1==0){
            step=d2/d1-1;
            if(d<=step)return updep+=d,Pos(z-(d2-d*d1)-d1,z-(d2-d*d1),z);
            else return updep+=step,up(z-2*d1,z-d1,z,d-step);
        }
        else{
            step=d2/d1;
            if(d<=step)return updep+=d,Pos(z-(d2-d*d1)-d1,z-(d2-d*d1),z);
            else return updep+=step,up(z-d2%d1-d1,z-d2%d1,z,d-step);
        }
    }
}
inline Pos up(const Pos&p,LL d){return up(p.x,p.y,p.z,d);}
 
inline void Sort(int&x,int&y,int&z){
    int d[3]={x,y,z};sort(d,d+3);x=d[0],y=d[1],z=d[2];
}
 
int main(){
    int x1,y1,z1,x2,y2,z2;
    scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);Sort(x1,y1,z1),Sort(x2,y2,z2);
 
    LL dep1,dep2;
    updep=0;Pos Root1=up(x1,y1,z1,1<<30);dep1=updep;
    updep=0;Pos Root2=up(x2,y2,z2,1<<30);dep2=updep;
 
    if(Root1!=Root2)puts("NO");
    else{
        puts("YES");
        if(dep1<dep2)swap(dep1,dep2),swap(x1,x2),swap(y1,y2),swap(z1,z2);
        Pos now1=up(x1,y1,z1,dep1-dep2),now2=Pos(x2,y2,z2);
 
        if(now1==now2)printf("%d",dep1-dep2);
        else{
            int L=0,R=dep2,mid;
            while(L<R){
                mid=(L+R+1)>>1;
                if(up(now1,mid)!=up(now2,mid))L=mid;else R=mid-1;
            }
            printf("%d",dep1-dep2+2*(L+1));
        }
    }
#ifndef ONLINE_JUDGE
    system("pause");
#endif
 
    return 0;
}