博弈论(NIM游戏——取石子)相关的题目

简介: 博弈论(NIM游戏——取石子)相关的题目

1.异或的性质

image.png

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


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;
}

6.1.png

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

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

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

其实不是,以为相同的数异或为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!

目录
打赏
0
0
0
0
8
分享
相关文章
|
5月前
|
猜数游戏(实现) 后附源码
本文介绍了如何使用C语言实现一个猜数游戏,包括游戏的逻辑流程、代码实现以及如何通过随机数生成器和时间戳生成一个1到100之间的随机数。
133 2
猜数游戏(实现) 后附源码
【植物大战僵尸杂交版】致敬传奇游戏玩家——一个普通人的六年坚持
【植物大战僵尸杂交版】致敬传奇游戏玩家——一个普通人的六年坚持
|
9月前
|
C++
【洛谷 P2670】[NOIP2015 普及组] 扫雷游戏 题解(模拟)
**扫雷游戏NOIP2015普及组题目:**在$n\times m$的雷区,玩家需避开地雷格(*),翻开非地雷格(?)显示周围地雷数。给定雷区布局,输出每个格子的地雷数或保持*不变。输入含雷区大小及布局,输出相应格式。样例输入/输出展示具体规则。100%数据$n,m\leq100$。程序思路:检查邻接8格,AC代码用C++实现。
62 0
设计一个三子棋游戏(下)
设计一个三子棋游戏(下)
设计一个三子棋游戏(上)
设计一个三子棋游戏(上)
110 0
通过游戏学Python系列之小兔要上天---手把手教你使用Pygame开发平台跳跃类游戏06之死亡后游戏重新开始
通过游戏学Python系列之小兔要上天---手把手教你使用Pygame开发平台跳跃类游戏06之死亡后游戏重新开始
233 0
通过游戏学Python系列之小兔要上天---手把手教你使用Pygame开发平台跳跃类游戏03之重力及碰撞检测
通过游戏学Python系列之小兔要上天---手把手教你使用Pygame开发平台跳跃类游戏03之重力及碰撞检测
224 0
每日一题——找出游戏的获胜者
每日一题——找出游戏的获胜者
135 0
每日一题——找出游戏的获胜者
【数学逻辑思维】好玩的数独游戏——001
标准数独是由一个给出了提示数字的9×9网络格组成的,我们只需要将其空格填上数字,使得每一行,每一列以及每一个3×3宫都没有重复的数字出现。并且每一道数独题都只有唯一的答案,它的规则简单但并不需要任何其他技巧。通过应用逻辑思维推理,得出空白格中的数字,从而提高数学逻辑思维。
142 0
【数学逻辑思维】好玩的数独游戏——001