10137. 「一本通 4.4 练习 4」跳跳棋

(Updated: )
oi
,

题意

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有三颗棋子，分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$（注意：棋子是没有区别的）。
跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

思路

可以将状态视为一个三元组$(x,y,z)$。

  1. 中间往左跳：$(x,y,z) –> (2x-y,x,z)$
  2. 中间往右跳：$(x,y,z) –> (x,z,2z-y)$
  3. 左边往右跳：$if (y-x)<(z-y) then (x,y,z) –> (y,2y-x,z) Because ‘Only one chess piece is allowed to be skipped at a time.’$
  4. 右边往左跳：$if (y-x)>(z-y) then (x,y,z) –> (x,2y-z,y) Because ‘Only one chess piece is allowed to be skipped at a time.’$

可以注意到，操作1与操作2可以使该三元组区间扩大。而操作3与操作4可以使三元组区间缩小。 那我们将区间扩大的视为父亲，区间缩小的状态视为儿子。 那么我们可以由此构建一棵树。 先把深度大的节点移到深度小的节点，然后二分到LCA的距离，往上走n步和求根。 当然，这样是会TLE的，比如说这组数据：9998 9999 10000000 如果以1步每次的速度的话就需要跳 (10000000-9999)/(9999-9998)次嘛！所以就有一个优化：MOD。 这样就可以像gcd一样，跑得飞快。省去了很多时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
#define int long long
#define MAXN 500010
using namespace std;
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
struct node{
    int x,y,z;
}endsss,tmps;
node make(int x,int y,int z){
    node pp;pp.x=x;pp.y=y;pp.z=z;return pp;
}
int GetFa(node p){
    int x=p.x,y=p.y,z=p.z,res=0;
    if(y-x<z-y){
        int pt=y-x;
        int zr=z-y;
        int kkk=zr%pt;res=zr/pt;
        if(kkk==0) --res,kkk+=pt;
        res+=GetFa(make(z-kkk-(y-x),z-kkk,z));
        return res;
        //-----X--Y-Z----------
    }else if(y-x>z-y){
        int pt=z-y;
        int zr=y-x;
        int kkk=zr%pt;res=zr/pt;
        if(kkk==0) --res,kkk+=pt;
        res+=GetFa(make(x,x+kkk,x+kkk+(z-y)));
        return res;
        //------X-Y---Z----------
    }else{
        endsss=p;
        return 0;
    }
}
void move(node p,int stp){
    int x=p.x,y=p.y,z=p.z;
    int pt=y-x,zr=z-y,cz,res=0;
    if(stp==0pt==zr){endsss=p;return ;}
    if(pt<zr){
        res=zr/pt;
        cz=zr%pt;
        if(cz==0) cz=pt,--res;
        if(stp<res) move(make(z-cz-(res-stp+1)*pt,z-cz-(res-stp)*pt,z),0);
        else move(make(z-cz-pt,z-cz,z),stp-res);
        //X,Y,Z
    }else{
        res=pt/zr;
        cz=pt%zr;
        if(cz==0) cz=zr,--res;
        if(stp<res) move(make(x,x+cz+zr*(res-stp),x+cz+zr*(res-stp+1)),0);
        else move(make(x,x+cz,x+cz+zr),stp-res);
        //X,Y,Z 
    }
}
int tmp[5];
void Sort(int &x,int &y,int &z){
    tmp[1]=x;tmp[2]=y;tmp[3]=z;
    sort(tmp+1,tmp+3+1);
    x=tmp[1];y=tmp[2];z=tmp[3];
}
int a,b,c;
int x,y,z;
bool judge(node q,node p){
    if(q.x==p.x&&q.y==p.y&&q.z==p.z) return 0;
    return 1;
}
bool check(int mid){
    move(make(x,y,z),mid);tmps=endsss;
    move(make(a,b,c),mid);
    if(judge(tmps,endsss)==1) return 0;
    return 1;
}
signed main(){
    a=read();b=read();c=read();
    x=read();y=read();z=read();
    Sort(x,y,z);
    Sort(a,b,c);
    int stp1=GetFa(make(a,b,c));tmps=endsss;
    int stp2=GetFa(make(x,y,z));
    if(judge(tmps,endsss)==1){
        puts("NO");
        return 0;
    }
    if(stp1<stp2) move(make(x,y,z),stp2-stp1),x=endsss.x,y=endsss.y,z=endsss.z;
    else if(stp1>stp2) move(make(a,b,c),stp1-stp2),a=endsss.x,b=endsss.y,c=endsss.z;
    int l=0,r=min(stp1,stp2),mid,ans;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    puts("YES");
    write(ans*2+abs(stp1-stp2));putchar('\n');
    return 0;
}
//(x,y,z) --> (2x-y,x,z)
//(x,y,z) --> (x,z,2z-y)
//if (y-x)<(z-y) then (x,y,z) --> (y,2y-x,z) Because 'Only one chess piece is allowed to be skipped at a time.'
//if (y-x)>(z-y) then (x,y,z) --> (x,2y-z,y) Because 'Only one chess piece is allowed to be skipped at a time.'