1 条题解

  • 0
    @ 2025-10-8 17:05:45
    #include <bits/stdc++.h>
    using namespace std;
    int d1, d2, d3, x, y, z, X, Y, Z, a[5];
    struct node{int x,y,z,tot;}A,B;
    
    inline void findroot(int x, int y, int z) {
        int 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=node{x,y,z,tot};
        else          A=node{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) {
        int 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() {
        scanf("%d%d%d", &a[1], &a[2], &a[3]);
        sort(a+1,a+4);x=a[1];y=a[2];z=a[3];
        scanf("%d%d%d", &a[1], &a[2], &a[3]);
        sort(a+1,a+4);X=a[1];Y=a[2];Z=a[3];
        
        findroot(x,y,z);findroot(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();
        int ans, tot;
        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;
            
        }
        int L=0, R=B.tot, c;
        while (L<=R) { 
            int mid=L+R>>1;
            if (check(mid, x, y, z, X, Y, Z)) c=mid, R=mid-1;//中间变量c记录最小的mid
            else L=mid+1;
        }
        printf("YES\n%d", ans+c*2);
        return 0;
    }
    
    • 1

    *【LCA最近公共祖先】[国家集训队] 跳跳棋

    信息

    ID
    3809
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    4
    已通过
    3
    上传者