BZOJ 2144 跳跳棋（LCA+欧几里德+二分答案）

发表于 |
字数统计: 1,191字 | 阅读时长 ≈ 5min

跳跳棋

问题描述

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

输入格式

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

输出格式

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

样例输入

1 2 3
0 3 5

样例输出

YES
2

提示

20% 输入整数的绝对值均不超过10
40% 输入整数的绝对值均不超过10000
100% 绝对值不超过10^9

用一个三元数对$(a,b,c)$表示当前棋子的位置，并且规定$a<b<c$，观察棋子位置的改变，

如果$b-a<c-b$，那么可以转移到 $(b,2b-a,c)$
反之，可以转移到 $(a,2b-c,b)$
此外，还可以转移到$(2a-b,a,c)$和$(a,c,2c-b)$

看起来很乱，但是注意到，$b$向两边跳与两边向$b$跳是互逆过程，因此我们不妨只考虑一个过程，考虑两边向中间跳的过程，那么每一个状态可以转移到的状态是唯一的，画个图就是
这里写图片描述
那么不难看出，从上往下走就是从中间往两边跳，从下往上走就是从两边往中间跳，于是，如果将每个状态看成一个节点，那么所有状态将会构成森林（注意不是树）

那么此题的解法也就比较明显了，即如果询问的两个节点不在一颗树中，那么无解，如果在一颗树中，最少跳动步数就是树上的距离。

那么接下来有两个问题，找根，和找lca

首先考虑找根，找根就是一个向上跳的过程，直到不能再向上跳，即$b-a=c-b$

那么不妨考虑一个节点$(x,y,z)$，令$a=y-x,b=z-y$
那么当$a<b$时，每次$x$跳到$y$，$z$中间，直到$a>b$，那么每次跳使$b$减少了$a$，不妨设跳了k次，那么有$k=(b-1)\div a$，注意不能是$b\div a$，因为$a=b$时不能跳，此时转移到了$(x+ka,y+ka,z)$
因此只需要模拟欧几里德算法的过程，直到$a=b$即可。

然后考虑找lca，找lca也是向上跳的过程，直到两个节点跳到同一个位置，注意到找根时可以算出深度，因此先将两个节点调整到同一深度，然后再二分跳的步数，如果跳到了同一个点，那么步数减小，反之步数增大，即可找到lca
至于向上跳，只需要在找根的向上跳的方法中加入一个步数限制即可。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
	ll x,y,z;
	void SO()
	{
		if(x>y)swap(x,y);
		if(x>z)swap(x,z);
		if(y>z)swap(y,z);
	}
};
bool operator==(node a,node b)
{return a.x==b.x&&a.y==b.y&&a.z==b.z;}
ll step,ans;
node A,B,C,D;
node GO(node p,ll cnt)
{
	ll k;
	for(step=0;cnt;step+=k)
	{
		ll a=p.y-p.x,b=p.z-p.y;
		if(a==b)return p;
		if(a<b)
		{
			k=min((b-1)/a,cnt);
			p.x+=k*a;p.y+=k*a;cnt-=k;
		}
		else
		{
			k=min((a-1)/b,cnt);
			p.y-=k*b;p.z-=k*b;cnt-=k;
		}
	}
	return p;
}
int main()
{
	ll i,j,k,a,b,L,R;
	scanf("%lld%lld%lld",&A.x,&A.y,&A.z);A.SO();
	scanf("%lld%lld%lld",&B.x,&B.y,&B.z);B.SO();
	C=GO(A,1e18);a=step;
	D=GO(B,1e18);b=step;
	L=1;R=min(a,b);
	if(C==D)puts("YES");
	else {puts("NO");return 0;}
	if(a<b)B=GO(B,b-a);
	else A=GO(A,a-b);
	ans=step;
	if(A==B){printf("%lld",ans);return 0;}
	while(L<=R)
	{
		k=L+R>>1;
		C=GO(A,k);D=GO(B,k);
		if(C==D)R=k-1;
		else L=k+1;
	}
	printf("%lld",ans+L*2);
}