洛谷题库 P1852 跳跳棋 题解与思路重现

洛谷题库 P1852 跳跳棋

我仍然坚持认为这道题不应该放在LCA的专题里面

一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊？我的第一反应是“递推出从某个状态开始能达到的所有状态”，时间复杂度大约是$\mathbf{O}(2^{|N|})$（至于为什么底数为$2$，请看完下一节后思考）。但很明显，坐标在$\pm 10^9$范围内的数据可容不下这般折腾。

但鉴于它被放在这个专题中，我们就尝试从树的角度来考虑。

首先，很容易想到的是，既然这些棋子可依照一定规律跳动，那么说明，当某组棋子的初始位置确定时，它们所有能够跳到的位置也能够确定。我们暂且将这些由位置组成的三元组称为状态，棋子的跳动产生的新位置称为转移。又因为题目中规定，“一颗棋子以另一颗棋子为中轴跳动，一次只能跳过一颗棋子”，说明每种状态只拥有至多三种转移方式——

• 中央棋子以右侧棋子为中轴向右跳动；
• 中央棋子以左侧棋子为中轴向左跳动；
• 左右棋子中，距离中央棋子的距离“严格”次大的一颗以中央棋子为中轴向另一侧跳动。

——为什么是“严格次大”？当两颗棋子与中间一颗距离相等时，谁也动不了，不可能跳到另一颗棋子身上。

我们再来考虑状态的转移。若是棋子向两边跳，可想而知有无限种转移方式，鬼才晓得它们能够跳到多远。我们就从第三种转移——能使它们距离缩小的方式来看。

我们暂且先不计算它们在数轴上的绝对位置。假设当前右侧棋子与中间的距离更大，左、右侧棋子距离中间分别为$x, y$个单位$(x < y)$，我们可以让左侧棋子向左跳一次。而因为棋子都是一样的，所以我们可以看作是左侧的两个棋子向右“平移”了$x$个单位。显而易见，只要现在右侧棋子与中间的间距更大，我们可以一直像这样平移，直到右侧棋子比左侧棋子距离中间更近。

现在你应该已经发现了——现在三个棋子之间的距离分别是$x, y \mod x$。而要是我们按照这个过程与给定的规则，一直迭代下去（图中右侧棋子左移，etc.）距离就会变为${x}\mod{y}, x\mod(y\mod x)$，……

这不就是欧几里得算法（辗转相除）求GCD（最大公约数）的过程吗？！

由欧几里得算法（$\forall a, b \in \mathbb{N}, \gcd (a, b) = \gcd (b, a\mod b)$）知，最终三个点之间的距离会“收束”到$x, y$的最大公约数$\gcd (x, y) = k$。这时，它们再无法向中间收束，我们把这种状态称为“原初状态”。现在我们考虑从原初状态“向外”转移，意即仅依照规则的第1、2条向外扩展。为什么不往回跳？因为显然，往回跳会转移到之前从原初状态扩展出的上一状态，是毫无意义的。由此，我们可以推导出由这个“原初状态”（间距$k, k$）能够迭代出的所有可能的状态：（现在我们暂时先不考虑它的绝对位置）

其中向下的子树是“向左跳”的转移，向上的则是“向右跳”的转移

这些状态的转移，就构成了一棵无限的二叉树。树上每两个状态之间的转移，都存在一条唯一的路径。最坏情况下，也可以跳回到“原初状态”，再向其子树逼近。

我们再回到原题上。现在，判断“是否能够通过给定状态转移到终止状态”，就可以通过判断初始和终止状态的棋子间距的最大公约数实现。那么，若是计算出$\gcd (|a-b|, |b-c|) = \gcd(|x-y|, |y-z|) = k$，它们就一定可以通过在同一棵树上的一些转移到达彼此的状态。

——我们刚才并没有讨论它们在数轴上的位置。试想，若是最终两个状态的“原初状态”的最大公约数$k$相同，但它们在数轴上的位置只相差$1$个单位，那也不可能相会。可以这样证明：因为每种状态向“原初状态”转移的时候有且仅有一种转移方式（向区间中央跳），在树上到根节点（原初状态）的路径也是唯一的，加入绝对位置后也一定存在唯一的对应关系；若有一种状态能够通过两个原初状态转移得到（即，从两个在数轴上位置不同的，但两两相距均为$k$的三元组），那么说明该状态存在两个向“原初状态”转移的方式（它是两棵“状态树”的子节点），明显与上述设定矛盾。所以，有且仅有一种方式可以从某一原初状态得到该状态。

而题目中第一问恰好是“判断能否在两个状态间互相转移”。所以，我们应当尝试先迭代到原初状态，检查它们的位置是否完全一样。

接下来，我们结合专题的名字——LCA，解答本题的第二问。若其二者原初状态完全相同，则它们一定都是以同一个原初状态为根的“状态树”上的节点。但是，对于这棵以数学迭代方式生成的树，我实在没有办法找到任意两个节点之间的直接联系（oeis.org或许真的有？）。

我们在之前计算它们的原初状态时，可以顺便求出它们在树上的深度。LCX、LTY dalao就采用了倍增：先将二者调整到同一深度，然后再二进制拆分倍增向上跳的步数，尝试向根节点迭代$2^k$步且使得二者不相会，最后两者向上跳一步就一定是LCA。

但每一次尝试倍增深度时，都要计算一次迭代后的结果，所以我们不妨直接采用二分答案的方式找到它们的最近公共祖先的深度。首先，答案具有一种特殊的“单调性”——它们的迭代结果不能比答案深的节点相会，而会在比答案浅的节点上相会。这两种结果的“分界点”就是答案。易知它们LCA的深度不会超过它们中深度较小的一个，所以我们二分的区间就是深度$[l, r]$ 即 $[0, \min(dep[a], dep[b])]$，我们假设答案为$mid = (l + r + 1) / 2$，查询答案合法性的方式就是将其二者同时迭代到该深度，并且检查其二者的状态。若最终各自完成迭代时不在同一节点上，说明LCA深度比预设的答案较深；反之则较浅。这时分别更新区间为$[mid, r]$，$[l, mid – 1]$并继续计算。

再来考虑计算迭代结果上的细节。因为我们将题述中的每一次操作都认为是一次迭代（事实上也确实如此），也就在树上增加了一层，所以若是真的一层一层跳，会顺利得到TLE的优秀结果。我们利用欧几里得算法的思想就能解决这个问题。有$\gcd (x ,y) = \gcd (y, x \mod y)$，所以我们每作一遍取模运算，就代表其已经向上跳了$\lfloor x / y \rfloor$层，同时记录迭代的步数即可。若是在作二分，则加上迭代次数限制（即，其深度减去预设答案深度$dep[x] – mid$）即可。欧几里得算法的平均复杂度大约是$\mathbf{O}(\log \min (x, y))$，这里有相关证明。

最终的时间复杂度似乎比较难计算。仅考虑二分与欧几里得算法，并且设节点深度为$\log N$的话，复杂度大约为$\mathbf{O}(\log^2 N)$，非常优秀。

献上因为实在不知道怎么传数组作参数并且懒得写第二个函数所以加了各种奇怪的限制而写得极丑的代码实现：

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
#include <bits/stdc++.h>
using namespace std;

int temp[3], s[3], e[3];
int res[6], step1, step2, l, r, mid;
int fin_step;

int check (int nums[], int divia, int dep_limit = INT_MAX) {
	int a = nums[1] - nums[0], b = nums[2] - nums[1] /* 两两间距 */, c, d, g, step = 0;
	while (a != b && dep_limit != 0) { // 未达成最小公约数状态
		if (a > b) { // 向右跳 
			d = a / b /* 理想迭代深度 */, c = a % b;
			if (d >= dep_limit) d = dep_limit, c = a - d * b; // 若迭代深度超出限制，则使用限制深度重新计算迭代后结果 
			if (c == 0) c = b, step += (d - 1), dep_limit -= (d - 1); // 若a是b的倍数，说明已经迭代到原初状态 
			else step += d, dep_limit -= d;
			nums[1] = nums[0] + c, nums[2] = nums[1] + b; // 更新棋子位置与距离差值 
			a = nums[1] - nums[0], b = nums[2] - nums[1];
		}
		else { // 向左跳 
			d = b / a, c = b % a;
			if (d >= dep_limit) d = dep_limit, c = b - a * d;
			if (c == 0) c = a, step += (d - 1), dep_limit -= (d - 1); else step += d, dep_limit -= d;
			nums[1] = nums[2] - c, nums[0] = nums[1] - a;
			a = nums[1] - nums[0], b = nums[2] - nums[1];
		}
	}
	for (int i = 0; i < 3; ++i)
		res[i + divia] = nums[i];
	return step;
}

int main () {
	/* 洛谷题库 P1852 / hwhw-倍增LCA L - 跳跳棋 吴秋实 */
	/* 它求的是通过GCD的变换在迭代中产生的结果的深度。 */
	scanf ("%d%d%d", &temp[0], &temp[1], &temp[2]);
	sort (temp, temp + 3); // 从小到大排序 
	s[0] = temp[0], s[1] = temp[1], s[2] = temp[2];
	step1 = check (temp, 0); // 状态1的深度 
	scanf ("%d%d%d", &temp[0], &temp[1], &temp[2]);
	sort (temp, temp + 3);
	e[0] = temp[0], e[1] = temp[1], e[2] = temp[2];
	step2 = check (temp, 3); // 状态2的深度 
	if (res[0] != res[3] || res[1] != res[4] || res[5] != res[2])  // 检查原初状态是否相同 
		return printf ("NO"), 0;
	else printf ("YES\n");
	// 迭代计算 + 二分实现LCA查找
	l = 0, r = min (step1, step2);
	while (l < r) {
		mid = (l + r + 1) >> 1;
		temp[0] = s[0], temp[1] = s[1], temp[2] = s[2];
		check(temp, 0, step1 - mid);
		temp[0] = e[0], temp[1] = e[1], temp[2] = e[2];
		check (temp, 3, step2 - mid);
		if (res[0] != res[3] || res[1] != res[4] || res[2] != res[5]) // 二者迭代后结果不同，调整深度到更浅处 
			r = mid - 1;
		else l = mid; // 结果相同，调整到更深处 
	}
	fin_step = step1 + step2 - (r << 1); // 最终需要的转移次数为其二者深度之和减去两倍LCA深度 
	printf ("%d", fin_step);

	return 0;
}

R53851045 记录详情