BZOJ2144: 跳跳棋【LCA+二分】

2144: 跳跳棋

【题目描述】

传送门

【题解】

一道非常好的题目。
设三元组(x,y,z)表示当前的位置。
接下来可以有四种跳法:
(x,z,z+(z-y))
(x-(y-x),x,z)
(y,y+(y-x),z)
(x,y-(z-y),y)
两种往里跳,两种往外跳,因为要满足x<y<z,所以当前往里跳的两种肯定只有一种可以跳,另一种不满足x<y<z。
所以我们可以将往里跳看成往父节点跳,忘外跳可以看出往儿子节点跳,这样就建出一棵树了,然后就是求树上最短路径,那么LCA就可以了。
当然每次不一定需要跳一步,在满足条件的情况下可以跳多次,如果(y-x)==(z-y)时就不能往里跳了。
先预处理到同一层,二分继续跳的层数就可以了。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
struct xcw{
    int x,y,z,Len;
    void read(){scanf("%d%d%d",&x,&y,&z);Len=0;if(x>y) swap(x,y);if(x>z) swap(x,z);if(y>z) swap(y,z);}
    bool operator ==(const xcw b){return x==b.x&&y==b.y&&z==b.z;}
}A,B,p,q;
xcw Get(xcw Now,int Step){
    for(int k=0;Step;Now.Len+=k){
        int L=Now.y-Now.x,R=Now.z-Now.y;
        if(L==R) return Now;
        if(L>R) k=min(Step,(L-1)/R),Now.y-=R*k,Now.z-=R*k,Step-=k;
        else k=min(Step,(R-1)/L),Now.x+=k*L,Now.y+=k*L,Step-=k;
    }
    return Now;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    A.read(),B.read();
    p=Get(A,1e9),q=Get(B,1e9);
    if(!(p==q)) return printf("NO\n"),0;else printf("YES\n");
    if(p.Len<q.Len) swap(A,B),swap(p,q);
    A=Get(A,p.Len-q.Len);
    int L,R,mid;
    for(L=0,R=1e9,mid=(R-L>>1)+L;L<=R;mid=(R-L>>1)+L) if(Get(A,mid)==Get(B,mid)) R=mid-1;else L=mid+1;
    printf("%d\n",p.Len-q.Len+L*2);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部