1 条题解

  • 0
    @ 2022-3-6 11:52:05

    一个比较巧妙的题。

    考虑每次跳跃只能跳过一个棋子,所以只有两种情况。

    一种是中间的向两边跳,一种是两边向中间跳。

    前者会让棋子的距离加大,后者会变小,考虑后者。

    容易发现两边向中间跳的方案是唯一的,离中间距离小的跳到另一边。

    如果两边距离相等,就不能向中间跳了。

    所以两个状态都一只向中间跳,看是否相等。

    考虑怎么找最小步数。

    假设 ba=x,cb=yb-a=x,c-b=y

    如果 x>yx>y,那么向中间跳两边的距离变成 xy,yx-y,y,实际上就是辗转相减。

    可以辗转相除优化一下。

    然后考虑两种状态一起跳,比如到了某个时候相等,找到那个状态即可。

    类似于找 LCA,先跳到深度相同,然后二分一下向上跳就好了。

    #include<bits/stdc++.h>
    using namespace std;
    struct Node{int a,b,c;};
    struct hzy{int l,r;};
    bool operator !=(Node a,Node b){return a.a!=b.a||a.b!=b.b||a.c!=b.c;}
    bool operator ==(hzy a,hzy b){return a.l==b.l&&a.r==b.r;}
    int Sum;
    Node get_rt(int a,int b,int c){
        int x=b-a,y=c-b;
        if(x==y)return (Node){a,b,c};
        if(x>y){
            int s=(x-1)/y;
            Sum+=s;
            return get_rt(a,b-s*y,c-s*y);
        }
        else{
            int s=(y-1)/x;
            Sum+=s;
            return get_rt(a+s*x,b+s*x,c);
        }
    }
    hzy jump(hzy a,int b){
        // cerr<<a.l<<' '<<a.r<<' '<<b<<endl;
        if(!b)return a;
        if(a.l>a.r){
            int s=(a.l-1)/a.r;
            if(s>b)return (hzy){a.l-b*a.r,a.r};
            return jump((hzy){a.l-s*a.r,a.r},b-s);
        }
        else{
            int s=(a.r-1)/a.l;
            // cerr<<s<<endl;
            if(s>b)return (hzy){a.l,a.r-b*a.l};
            return jump((hzy){a.l,a.r-s*a.l},b-s);
        }
    }
    int a[5],b[5],ans,sum1,sum2;
    int main(){
        for(int i=1;i<=3;i++)scanf("%d",&a[i]);
        for(int i=1;i<=3;i++)scanf("%d",&b[i]);
        sort(a+1,a+4),sort(b+1,b+4);
        Node rt1=get_rt(a[1],a[2],a[3]);sum1=Sum,Sum=0;
        Node rt2=get_rt(b[1],b[2],b[3]);sum2=Sum;
        if(rt1!=rt2)return puts("NO"),0;
        hzy p,q;
        p.l=a[2]-a[1],p.r=a[3]-a[2],q.l=b[2]-b[1],q.r=b[3]-b[2];
        if(sum2>sum1)swap(sum1,sum2),swap(p,q);
        // cerr<<q.l<<' '<<q.r<<' '<<p.l<<' '<<p.r<<endl;
        if(sum1>sum2){
            ans+=sum1-sum2;
            p=jump(p,sum1-sum2);
        }
        int l=0,r=sum2;
        // cerr<<q.l<<' '<<q.r<<' '<<p.l<<' '<<p.r<<endl;
        while(l+1<r){
            int mid=l+r>>1;
            if(jump(p,mid)==jump(q,mid))r=mid;
            else l=mid;
        }
        if(jump(p,l)==jump(q,l))ans+=l*2;
        else ans+=r*2;
        puts("YES");
        printf("%d",ans);
        return 0;
    }
    
    • 1

    信息

    ID
    88
    时间
    500ms
    内存
    259MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者