题解：P8606 [蓝桥杯 2013 国 B] 高僧斗法

minecraftbucuo · 2024-12-14 15:28:09 · 题解

前言：

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

Nim 博弈：

nim 博弈介绍

阶梯博弈：

阶梯博弈介绍

解题思路：

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

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

解法的进一步说明：

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

写一个判断先手是否能赢的函数，先手能赢则返回 true，否则返回 false。判断方法为计算奇数层石子的异或和，如果异或和为 0 则先手必败，否则必胜（SG 定理）。
录入数据后，计算出相邻两人直接的阶梯数量，记录在一个数组中。而此数组就是作为判断输赢的依据。
当判断完先手必胜时，考虑暴力枚举所有可能的走法，遍历第一个人到倒数第二个人，对于每一个人，向上步数从走 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;
}

结语：

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