博弈论（NIM游戏——取石子）相关的题目-Toy模板网

这篇具有很好参考价值的文章主要介绍了博弈论（NIM游戏——取石子）相关的题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

文章来源地址https://www.toymoban.com/news/detail-422390.html

1.异或的性质

博弈论（NIM游戏——取石子）相关的题目

🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈

2.nim游戏（基础）

891. Nim游戏 - AcWing题库

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

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

输入格式

第一行包含整数 n。

第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。

输出格式

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

否则，输出 No。

例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。

操作步骤：
1. 先手从第二堆拿走1个，此时第一堆和第二堆数目相同
2. 无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可。

先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0

#include <iostream>
#include <cstdio>
using namespace std;

/*
先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/

int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
}

3.nim游戏（变形）

892. 台阶-Nim游戏 - AcWing题库

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

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

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

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

输入格式

第一行包含整数 n。

第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai

输出格式

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

否则，输出 No。

此时我们需要将奇数台阶看做一个经典的Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

证明：
先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手
于是轮到后手：
①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0

只异或奇数的，不异或偶数的，因为最后要把石子都放到地面，地面是第0层（偶数层，如果算上地面的，也许会多一层，个人理解）

#include <iostream>
using namespace std;

int main()
{
    int res = 0;
    int n;
    cin >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        int x;
        cin >> x;
        if(i % 2==1) res ^= x;//只异或奇数的
    }

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

博弈论（NIM游戏——取石子）相关的题目

⭐⭐⭐代码中，先都异或了一遍，然后把

修改的位置的原来的数和修改了的数又异或了一遍

刚开始以为这不是重复了吗

其实不是，以为相同的数异或为0，0异或任何数还为原数

那么 修改的位置的原来的数异或后是0，并不影响

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5+5;

int a[N];

signed main(){
    int n,q,x,y;
    cin>>n>>q;
    
    int sum = 0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum^=a[i];
    }
    
    while(q--){
        cin>>x>>y;
        sum^=a[x];
        sum^=y;
        a[x] = y;
        if(sum!=0){
            cout<<"Kan"<<endl;
        }
        else{
            cout<<"Li"<<endl;
        }
    }
    
    return 0;
}

Code over！

到了这里，关于博弈论（NIM游戏——取石子）相关的题目的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！