博弈论-台阶Nim游戏

46 阅读 0 评论 31 点赞

我是靠谱客的博主独特蜻蜓，最近开发中收集的这篇文章主要介绍博弈论-台阶Nim游戏，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题：

现在，有一个nn级台阶的楼梯，每级台阶上都有若干个石子，其中第ii级台阶上有aiai个石子(i≥1i≥1)。

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

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

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

根据样例对问题分析：

Nim游戏通用原理：

给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

Method

定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0

方法：找奇数台阶，如果奇数台阶异或！=0,则胜利。

充要条件：所有奇数级台阶所有石子异或起来不等于0.

Example

输入格式

第一行包含整数nn。

第二行包含nn个整数，其中第ii个整数表示第ii级台阶上的石子数aiai。

输出格式

如果先手方必胜，则输出“Yes”。

否则，输出“No”。

数据范围

1≤n≤1051≤n≤105,
1≤ai≤1091≤ai≤109

输入样例：

3
2 1 3

输出样例：

Yes

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    int res = 0;
    
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++)
    {
        int x;
        scanf ("%d", &x);
        if (i % 2) res ^= x;//所有奇数级台阶所有石子异或起来不等于0.
    }
    
    if (res) puts("Yes");
    else puts("No");
    
    return 0;
}