题解：P16251 [蓝桥杯 2026 省研究生组] 基态坍缩

jlhj · 2026-04-27 09:32:18 · 题解

一道十分基础的博弈论。

我们可以采用逆向思维，考虑每个节点在成为末端节点时的先手胜负状态。我们定义 w[i] 表示当前节点 i 变为末端节点（能级初始值为 f[i]）在当前节点的胜负状态。

我们从最后一个节点开始递推：

当节点 i 成为末端时，当前玩家可以对其降级，设当前能级为 b，所以 b = f[i]。

如果 b = 1，当前玩家只能将其降至 0，而现在的末端节点 i - 1 是由对手操作的，因此 w[i] 与 w[i - 1] 状态相反。

如果 b > 1，当前玩家可以将其变成 1，这样对手就要操作这个 1，把它降为 0，这样当前玩家就可以取得在节点 i - 1 上的先手并控制在节点 i - 1 上的先手，因此 w[i] = 1。

所以我们可以从 i = 1 开始递推，而 w[n] 就是先手的胜负情况。

注：当节点 1 为末端节点时，显然先手必胜，因为节点 1 没有前驱节点，故 w[i] = 1。

由逆向思维得出递推关系后，我们要用正向递推实现，因为递推关系是依赖于 f[i - 1]，而使用逆向递推则依赖于 f[i + 1]，会得到错误的结果。

最后贴出我丑陋的代码：

#include <iostream>
#include <vector>
using namespace std;
int t;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> f(n);
        for (int i = 0; i < n; i++) {
            cin >> f[i];
        }
        bool w = 1;  
        for (int i = 1; i < n; i++) {
            if (f[i] == 1) {
                w = !w;  
            }
            else {
                w = 1;  
            }
        }
        cout << (w ? "L" : "Q") << "\n";
    }
    return 0;
}