跳跳棋(9018_1563)(BZOJ_2144)

向右看齐 2021-09-30 14:22 137阅读 0赞

题目：

Hzwer的跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。

某一天，黄金大神和cjy用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。他们要通过最少的跳动把它们的位置移动成x，y，z。（棋子是没有区别的）

跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。

写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

这道题的状态是可以在树上处理的，对于一个中间到两端距离不等的点，我们把中间的点向左跳作为它的左子树，向右跳作为右子树，同理，一个节点的父亲就是距中间点较近的点向另一边跳，显然，当且仅当两状态所属的节点有公共祖先时题目有解，输出步数只需要跑lca将目标节点和初始节点到根的距离减去最近公共祖先到根的距离的两倍即可。实现中注意用gcd来处理向上追溯的过程。

#include <cstdio>
    #include <cstring>
    #define swap(a,b) swaps=a,a=b,b=swaps;
    #define lcas(a,b,c,g) gcdlca(b-a>c-b?b-a:c-b,b-a<=c-b?b-a:c-b,b-a>c-b?-1:1,g,a,b,c); 
    #define min(a,b) a<b?a:b
    using namespace std;
    int ansabc=0,ansxyz=0,ans=0;
    int aa,bb,cc,xx,yy,zz,swaps;
    bool gcdlca(int q,int p,short int k,int g,int &x,int &y,int &z){
        int r=q%p;
        int l=q/p;
        if(r==0){
            l--;
            r=p;
            if(k==1){
                if(l>=g){
                    y=z-r-p*(l-g);
                    x=z-r-p*(l-g+1);
                    return true;
                }
                y=z-r;
                x=y-p;
                ansabc+=l;
                return false;
            }
            else{
                if(l>=g){
                    y=x+r+p*(l-g);
                    z=x+r+p*(l-g+1);
                    return true;
                }
                y=x+r;
                z=y+p;
                ansabc+=l;
                return false;
            }
        }
        if(k==1){
            if(l>g){
                y=z-r-p*(l-g);
                x=z-r-p*(l-g+1);
                return true;
            }
            y=z-r;
            x=y-p;
            ansabc+=l;
            gcdlca(p,r,-1,g-l,x,y,z);
        }
        else{
            if(l>g){
                y=x+r+p*(l-g);
                z=x+r+p*(l-g+1);
                return true;
            }
            y=x+r;
            z=y+p;
            ansabc+=l;
            gcdlca(p,r,1,g-l,x,y,z);
        }
    }
    int lca()
    {
        int a2,b2,c2,x2,y2,z2,a3=aa,b3=bb,c3=cc;
        int a1=a2=aa,b1=b2=bb,c1=c2=cc,x1=x2=xx,y1=y2=yy,z1=z2=zz;
        lcas(x1,y1,z1,0x7fffffff);
        ansxyz=ansabc; ansabc=0;
        lcas(a1,b1,c1,0x7fffffff);
        if(!(a1==x1&&b1==y1&&c1==z1)){
            printf("NO\n");
            return -1;
        }
    //    printf("%d\n",ansabc);
    //    printf("%d\n",ansxyz);
        int t;
        if((ansabc-ansxyz)>0)
            t=ansabc-ansxyz;
        else
            t=ansxyz-ansabc;
        ans=ansabc+ansxyz;
        int ll=min(ansabc,ansxyz);
        for(int i=0; i<=30; i++)
            if((1<<i)&t){
                if(ansxyz>ansabc){
                    lcas(x2,y2,z2,1<<i);
                }    
                else lcas(a2,b2,c2,1<<i);
            }
        a3=a2;b3=b2;c3=c2;
        for(int i=30; i>=0; i--)
        {
            if(!(a2==x2&&b2==y2&&c2==z2)&&ll>=(1<<i))
            {
                //printf("%d\n",i);
                aa=a2,bb=b2,cc=c2;
                xx=x2;yy=y2;zz=z2;
                lcas(x2,y2,z2,1<<i);
                lcas(a2,b2,c2,1<<i);
                if(a2==x2&&b2==y2&&c2==z2){
                    a3=a2;b3=b2;c3=c2;
                    a2=aa,b2=bb,c2=cc;
                    x2=xx;y2=yy;z2=zz;
                    continue;
                }
                ll-=(1<<i);
            }
        }
        ansabc=0;
        //printf("%d\n%d\n%d\n",a3,b3,c3);
        lcas(a3,b3,c3,0x7fffffff);
        return ans-2*ansabc;
    }
    void sso(int &a,int &b,int &c){
        if(a>b) swap(a,b);
        if(b>c) swap(b,c);
        if(a>b) swap(a,b);
        return ;
    }
    int main() {
        scanf("%d%d%d%d%d%d",&aa,&bb,&cc,&xx,&yy,&zz);
        sso(aa,bb,cc);
        sso(xx,yy,zz);
        //printf("%d%d%d%d",a,b,c,ansabc);
        //printf("%d%d%d%d",x,y,z,ansxyz);
        int yyyy=lca();
        if(yyyy==-1) return 0;
        else printf("YES\n%d",yyyy);
        return 0;
    }

转载于:https://www.cnblogs.com/JiuPleber/p/7152728.html