202503021817 博弈论 台阶 奇偶

台阶 奇偶

现在，有一个  $n$  级台阶的楼梯，每级台阶上都有若干个石子，其中第  $i$  级台阶上有  $a_i$  个石子$(i\ge 1)$。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

思路

根据 Nim 游戏定理, 让所有可以拿的石子数相异或为 0 就可以先手必胜。

但这里除了台阶 1, 其他台阶的石子只能合并到下一个台阶上。

怎样保证自己一定有石子拿呢？ 把奇数的台阶看做 Nim 游戏, 全异或为 0 时必输。 若对手移动偶数台阶的数, 则我们把他移动过的再移动到下一个台阶, 不会影响奇数台阶的性质。 若队友移动奇数台阶的数, 根据 Nim 游戏, 我们总能找到一种移动方案来使奇数台阶异或为 0。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int main()
{
    int n, x;
    cin >> n;
    cin >> x;
    for(int i = 2; i <= n;i++)
    {
        int t;
        cin >> t;
        if(i % 2) x ^= t;
    }
    if(x) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}