Imperceptible

BZOJ2144

Word count: 1.1kReading time: 5 min
2018/10/17 Share

BZOJ2144

Description

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

Input

第一行包含三个整数,表示当前棋子的位置a b c。(互不相同)
第二行包含三个整数,表示目标位置x y z。(互不相同)

(输入数据均在$10^9$内)

Output

如果无解,输出一行NO。如果可以到达,第一行输出YES,第二行输出最少步数。
Image text

Sample Input

1
2
1 2 3
0 3 5

Sample Output

1
2
YES
2

Solution

对于一个三元组作为状态$a,b,c$考虑能够转移到的所有状态再来判和$x,y,z$是否相同的暴搜肯定是过不了这题的。然后尝试找找规律,如果一个状态$(a,b,c)$中$(a<b<c下同)$

则只能转移到

两种状态,而如果不等的话只能选一边跳(因为只允许跳过一个棋子),$(不妨令a-b>c-b)$共有三个转移

冷静分析,什么东西是特殊点两个”转移“普通点三个”转移“?
二叉树!
(这题来说树就够了)
这一步想通了之后的就简单了
相当于每个状态都是树上的节点,可能转移到与之相邻的节点,特殊点就是两个转移的的点即为根,1问相当于问是否同属一个树,2问相当于求两点之间距离,用求LCA的方法即可。
还有一个问题就是可能两个点之间距离太小如数据$(0,1,99999999)$可能要很久才会到达一个根,考虑每次转移的两个距离$(x,y)$到$(x,y-x)$直到$x=y$发现相当于每次减了若干小的那个数,可以算出能够减多少次和当前往上跳的次数取min来直接减去以加速这个过程,代码如下:

Code

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
#include<bits/stdc++.h>
#define FIO "2144"
#define DBUG(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;
const int N=4;
using namespace std;
template <class T>inline void read (T &x) {
T f=1;
x=0;
char ch=getchar();
for (; !isdigit (ch)&&ch!='-'; ch=getchar());
if (ch=='-')f=-1,ch=getchar();
for (; isdigit (ch); ch=getchar())x=x*10+ch-'0';
x*=f;
}
struct node {
int v[N];
inline int& operator [] (int x) {
return v[x];
}
inline void rd() {
read (v[1]); read (v[2]); read (v[3]);
if (v[1]>v[2]) swap (v[1],v[2]);
if (v[2]>v[3]) swap (v[2],v[3]);
if (v[1]>v[2]) swap (v[1],v[2]);

}
bool operator == (const node &t)const {
return v[1]==t.v[1] && v[2]==t.v[2] && v[3]==t.v[3];
}
void operator = (node t) {
v[1]=t[1]; v[2]=t[2]; v[3]=t[3];
}
} a,b;
int L,R,mid,cur,d1,d2,ans;
node up (node x,int step) {
int k1,k2;
if ((k1=x[2]-x[1])== (k2=x[3]-x[2])) return x;
node ret=x;
if (k1>k2) {
int delta=min (step, (k1-1)/k2);
step-=delta; cur+=delta;
ret[2]=ret[2]-delta*k2; ret[3]-=delta*k2;
} else {
int delta=min (step, (k2-1)/k1);
step-=delta; cur+=delta;
ret[2]+=delta*k1; ret[1]+=delta*k1;
}
return step?up (ret,step):ret;
}
int main() {
freopen (FIO".in","r",stdin);
freopen(FIO".out","w",stdout);
a.rd(); b.rd();
cur=0; node x=up (a,INF); d1=cur;
cur=0; node y=up (b,INF); d2=cur;
if (x==y) {
puts ("YES");
if (d1<d2) swap (d1,d2),swap (a.v[1],b.v[1]),swap (a.v[2],b.v[2]),swap (a.v[3],b.v[3]);
a=up (a,d1-d2);
L=0; R=d2; ans+=d1-d2;
while (L<=R) {
mid= (L+R)>>1;
if (up (a,mid)==up (b,mid)) R=mid-1;
else L=mid+1;
}
printf ("%d",ans+ (L<<1));
} else puts ("NO");
return 0;
}
CATALOG
  1. 1. BZOJ2144
    1. 1.0.1. Description
    2. 1.0.2. Input
    3. 1.0.3. Output
    4. 1.0.4. Sample Input
    5. 1.0.5. Sample Output
    6. 1.0.6. Solution
    7. 1.0.7. Code