博弈论

_HHJ · 2022-06-19 22:32:34 · 个人记录

相关例题:nim游戏

Nim 游戏

题目

甲，乙两个人玩 nim 取石子游戏。

nim 游戏的规则是这样的：地上有 n 堆石子（每堆石子数量小于 10^4），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 n 堆石子的数量，他想知道是否存在先手必胜的策略。

我们把这种游戏称为NIM博弈，游戏中面临的状态称为局面，第一个行动的称为先手，第二个行动的称为后手, NIM博弈不存在平局只存在先手必胜和先手必败的两种情况。

• 先手必胜状态: 可以走到某一个必败状态
• 先手必败状态: 走不到任何一个必败状态

当

先手必败

先手必胜

可得，我们只需把所有石头\mathbb{\large\color{red}\oplus}异或起来即可

那么如何证明正确性？

假设到最后一步，即所有石头都妹有了，我们不能进行任何操作

另一种情况

假设\large \mathbb{\color {orange}X}的二进制最高的1位在第\large\mathbb\green{K}位，那么\large \mathbb {\color{blue} A_1 \sim A_k}位上一定存在\large \mathbb \color{blue}A_i它的第\large\mathbb\green{K}位为1 显然\large \mathbb{{\color {blue}A_i} {\color {red} \oplus} x_i <{\color{blue} A_i}}

由于我们可以拿走\large \mathbb{{\color {blue}A_i} - ({\color {blue}A_i} {\color {red}\oplus} {\color {orange}X})}使 {\large \mathbb\color {blue}A_i}变成\large \mathbb{}{{\color {blue}A_i}{{\color {red}\oplus} {\color {orange}X}}}

对于任何一个局面，若

那么无论如何拿石头得到局面下石头异或和都不为0 我们可以用反证法:

将

与不能不取石头矛盾

证毕

代码如下

#include <iostream>

using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,res = 0;
        scanf("%d",&n);
        while(n--)
        {
            int x;
            scanf("%d",&x);
            res ^= x;

        }
        if(res)puts("Yes");
        else puts("No");
    }
    return 0;

}