自动搬运

查看原文

来自洛谷，原作者为

	minecraftbucuo 我的世界，不错！

搬运于2025-08-24 22:40:38，当前版本为作者最后更新于2024-12-14 15:28:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：

这道题其实是 nim 博弈的进阶版：阶梯博弈。

Nim 博弈：

nim 博弈介绍

阶梯博弈：

阶梯博弈介绍

解题思路：

了解了 nim 博弈和阶梯博弈后，我们发现这道题只需将每对相邻的两个人看成一个阶梯，把这两人之间的阶梯数量看作是石子的数量，那么最左边人向右移动相当于把第一个阶梯的石子移动到地面，中间的人（除了最左边和最右边的人）向右移动相当于把当前阶梯的石子移动到它左边的台阶，刚好和阶梯博弈中的规则一一对应。

于是，根据阶梯博弈中的结论（不知道的话请看上面的链接），我们首先对奇数层做 nim 博弈，算出其异或和的值，如果是 $0$ 的话直接输出 $-1$，否则一定有一种移动方法可以使移动后异或和为 $0$，这里暴力枚举即可。

解法的进一步说明：

可能是还不够详细，被打回来了。所以在此补充进一步说明。

1. 写一个判断先手是否能赢的函数，先手能赢则返回 true，否则返回 false。判断方法为计算奇数层石子的异或和，如果异或和为 $0$ 则先手必败，否则必胜（SG 定理）。

2. 录入数据后，计算出相邻两人直接的阶梯数量，记录在一个数组中。而此数组就是作为判断输赢的依据。

3. 当判断完先手必胜时，考虑暴力枚举所有可能的走法，遍历第一个人到倒数第二个人，对于每一个人，向上步数从走 $1$ 格到走最远格数进行遍历：

for (int i = 0; i < n - 1; i++) {
  for (int j = 1; j <= a[i + 1] - a[i] - 1; j++) {
    // 判断当前走法是否可行代码。
  }
}

• 当 $i$ 为偶数时，相当于在下标为 $i$ 的阶梯减少 $j$ 个石子，然后判断移动方法是否可行，不可行的话需要还原为初始状态：

b[i] -= j;
// 判断此移动方法是否可行代码。
b[i] += j;

• 当 $i$ 为奇数时，相当于在下标为 $i - 1$ 的阶梯增加 $j$ 个石子，其他逻辑同上：

b[i - 1] += j;
// 判断此移动方法是否可行代码。
b[i - 1] -= j;

最后展示一下完整的代码。

Code：

#include <bits/stdc++.h>
using namespace std;

bool is_win(vector<int>& b) {  // 当前石子数量为 b 数组情况下先手能赢则为 ture。
	int sum = 0;
	for (int i = 0; i < (int)b.size(); i += 2) { // 只需算奇数层的异或和，所以 i += 2。
		sum ^= b[i];
	}
	return sum != 0;
}

int main() {
	int n;
	vector<int> a;
	while (cin >> n) {
		a.push_back(n);
	}
	n = a.size();
	vector<int> b(n - 1);
	for (int i = 0; i < n - 1; i++) b[i] = a[i + 1] - a[i] - 1;
	if (!is_win(b)) cout << -1 << endl; // 先手不能赢则直接输出 -1。
	else {
		for (int i = 0; i < n - 1; i++) {
			for (int j = 1; j <= a[i + 1] - a[i] - 1; j++) {
				if (i & 1) {
					b[i - 1] += j; // 相当于当前阶梯石子移动 j 个到前一个阶梯。
					if (!is_win(b)) { // 刚才的后手是现在的先手，他得输。
						cout << a[i] << ' ' << a[i] + j << endl;
						return 0;
					}
					b[i - 1] -= j; // 还原原来的状态，除非前面已经得出了答案。
				} else {
					b[i] -= j;
					if (!is_win(b)) {
						cout << a[i] << ' ' << a[i] + j << endl;
						return 0;
					}
					b[i] += j;
				}
			}
		}
	}
	
	return 0;
}

结语：

本题关键在于能想到转化为阶梯博弈模型。另外，本人代码和题解可能比较屎，有错误欢迎指正，希望大佬们不要嘲笑 ಥ_ಥ。