【bzoj2144】跳跳棋

2014年10月22日3,3200

Description

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

写一个程序,首先判断是否可以完成任务。如果可以,输出最少需要的跳动次数。

Input

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

Output

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

Sample Input

1 2 3
0 3 5

Sample Output

YES
2
【范围】20% 输入整数的绝对值均不超过1040% 输入整数的绝对值均不超过10000100% 绝对值不超过10^9

题解

首先广搜有20分

对于一个状态

例如2 3 7

中间可以往两侧跳,即2 3 7->1 2 7 / 2 3 7->2 7 11

两侧仅有一个能往中间跳,即2 3 7->3 4 7

那么所有的状态就能表示为一棵二叉树,第一种情况为其两个儿子,第二种为其父亲

问题转换为给定树上的两个结点,求其距离

直接暴力可以得40分

可以构造这样的数据

1 2 1000000000

99999998 99999999 1000000000

这样左边要一直往中间跳上上亿次

我们发现若记前两个数差t1,后两个数差t2,不妨设t1<t2

则左边最多往中间跳(t2-1)/t1次

然后只能右边往中间跳,是一个辗转相除的过程,即在logK的时间内我们可以用这种方法得到某个结点它向上K次后的结点,或者根节点,同时还可以顺便算下深度

那么只要求始终两个状态的深度d1,d2,将较深的调整到同一深度

然后二分/倍增求与lca的深度差x

ans=2*x+abs(d1-d2)