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

题意

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有三颗棋子,分别在 $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.'