P1852 跳跳棋 题解

发表于
很经典的 LCA 题

题目链接

题意

棋盘上有3颗棋子，分别在 $a$，$b$，$c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x$，$y$，$z$。

跳动的规则：任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。

先研究一下跳动

我们发现，对于每组确定的位置，跳动只有以下3种情况：

  • 中间的往两边跳，分别是 $(x,y,z)->(x,2x-y,z)$ 和 $(x,y,z)->(x,2z-y,z)$；

  • 两边的往中间跳，是 $(x,y,z)->(2y-x,y,z)$ 和 $(x,y,z)->(x,y,2y-z)$ 中的一个。

任何时候都可以有3种情况吗？

并不是！我们发现当两边的棋子与中间的棋子距离相等时，是不能往中间跳的。这时只有中间往两边跳的情况。

而且容易证明，对于一组初始位置，满足两边的棋子与中间的棋子距离相等的目标位置是唯一的。

那么判断能否完成跳动就比较简单了，只需把 $(a,b,c)$ 与 $(x,y,z)$ 都移动到唯一的目标位置，若相同就是可以完成的。（个人觉得和最小表示法的思想有那么一点点类似）

再研究一下跳动

注意到本题的数据范围是1e9，我们没办法每次暴力地把两边的棋子往中间移动。

但是注意这种情况：

有没有感觉其实和跳动的次数并没有太大关系，我们只关心模数！

我们令 $d_1,d_2$ 分别表示左边两个数之间的距离与右边两个数之间的距离。

我们钦定 $d_1<d_2$，大于的情况同理。

发现每次可以跳过 $d_1$ 的距离，最多能跳 $d_2-1$ 的距离。令$k=(d_2-1)/d_1$，因此由 $(x,y,z)$ 可以跳到 $(x+k\times d_1,y+k\times d_1,z)$。

这样我们就得到了一种快速跳跃的方法。

注意到这里所说的跳跃，其实不一定非要跳跃到无法再跳，我们可以在实现的过程中钦定跳跃的步数，同样能 $O(1)$ 的完成跳跃。

然后研究一下状态集合

前文提到，对于每个状态集合，有唯一的状态使得它只能向两种状态转移，其余的状态都可以向三种状态转移。如果把每个状态抽象成一个点，那么状态之间的关系将构成一颗二叉树！

那我们要解决的问题就变成了求树上两个点的LCA。

常用的倍增求LCA肯定是不行的，因为状态过多存不下。

我们考虑改进这个方法。求LCA需要求出深度，在这个问题中也就是从根节点跳跃成当前状态需要跳的步数。我们在把初始状态跳到根判断是否在同一棵树上时可以顺便处理深度。倍增的第一步是将两个点移动到同一深度，这一步显然应当保留。

第二步是找到同一深度两个点的LCA。倍增虽然无法处理，但是我们都知道两个点的公共祖先满足单调性！于是我们可以二分答案，再判断是否跳到同一个点上。这个过程很容易实现。

于是这道题就完美的做完啦！

复杂度

每次跳跃的复杂度最坏为 $O(logn)$，外面套一个二分是 $O(logn)$，因此最终的复杂度应该为 $O(log^2n)$。

代码

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct dot{
	int x,y,z,dep;
}A,B;
int a[5],ans,b[5];
void jump(dot &a,int stp){
	while(stp){
		int d1=a.y-a.x,d2=a.z-a.y;
		if(d1==d2)break;
		if(d1<d2){
			int d3=min(stp,(d2-1)/d1);
			stp-=d3;
			a.x+=d3*d1,a.y+=d3*d1;
		}
		else{
			int d3=min(stp,(d1-1)/d2);
			stp-=d3;
			a.z-=d3*d2,a.y-=d3*d2;
		}
	}
}
dot dfs(int x,int y,int z){
	int dp=0;
	while(1){
		int d1=y-x,d2=z-y;
		if(d1==d2)break;
		if(d1<d2){
			int d3=(d2-1)/d1;
			dp+=d3;
			x+=d3*d1,y+=d3*d1;
		}
		else{
			int d3=(d1-1)/d2;
			dp+=d3;
			z-=d3*d2,y-=d3*d2;
		}
	}
	dot ret=(dot){x,y,z,dp};
	return ret;
}
signed main(){
	for(int i=1;i<=3;i++)cin>>a[i];
	sort(a+1,a+4);
	A=dfs(a[1],a[2],a[3]);
	for(int i=1;i<=3;i++)cin>>b[i];
	sort(b+1,b+4);
	B=dfs(b[1],b[2],b[3]);
	if(A.x!=B.x||A.y!=B.y||A.z!=B.z){
		puts("NO");
		return 0;
	}
	A.x=a[1],A.y=a[2],A.z=a[3];
	B.x=b[1],B.y=b[2],B.z=b[3];
	if(A.dep<B.dep)swap(A,B);
	ans=A.dep-B.dep;
	jump(A,A.dep-B.dep);
	int l=0,r=A.dep;
	while(l<r){
		int mid=(l+r)>>1;
		dot NA=A,NB=B;
		jump(NA,mid),jump(NB,mid);
		if(NA.x==NB.x&&NA.y==NB.y&&NA.z==NB.z)r=mid;
		else l=mid+1;
	}
	ans+=l*2;
	puts("YES");
	cout<<ans;
	return 0;
}

参考资料

该题题解区的前三排题解。