当前位置:首页 » 《随便一记》 » 正文

【c++/java】Nim游戏(博弈论证明)_AcWing-leimingze的博客

22 人参与  2021年12月17日 14:16  分类 : 《随便一记》  评论

点击全文阅读


891.Nim游戏

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

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

输入格式
第一行包含整数 n。

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

输出格式
如果先手方必胜,则输出 Yes。

否则,输出 No。

数据范围
1≤n≤105,
1≤每堆石子数≤109
输入样例:
2
2 3
输出样例:
Yes
本题思路
公平组合游戏:
若一个游戏满足:

  • 由两名玩家交替行动
  • 在游戏进行的任意时刻,可以执行合法行动与轮到哪位玩家无关
  • 不能行动的玩家判负

eg:围棋不是公平组合游戏
解释必胜状态和必败状态:
必胜状态:先手进行某一特定操作,留给后手的只有失败,对于先手来说是必胜状态
必败状态:先手无论如何操作,留给后手的只有必胜状态,对于先手来说是必败状态
操作步骤
分别有两堆:2,3

  • 先手从第二堆拿走一个,此时第二堆与第一堆数目相同
  • 无论后手怎么拿,先手对后手镜像操作,即后手与先手操作相同

本题结论
假设n堆石子,分别为a1,a2,a3,……,an,如果a1⊕ a2⊕ a3⊕,……,⊕ an≠0,先手必胜,否则先手必败.
最终结果0⊕0⊕0⊕0,……,⊕0=0
结论证明
在操作过程中,如果a1⊕ a2⊕ a3⊕,……,⊕ an=x≠0,那么玩家一定会通过拿走某一堆中的石子导致结果变为零。

  • 证明:假设x的二进制最高不为0位在第k位,在a1,a2,……an种必有一个ai,ai的第k位为1,使得ai⊕x<ai;
    在这里插入图片描述
    那么从第i堆拿走(ai-ai⊕x)个石子后,第i堆还剩ai-(ai-ai⊕x)=ai⊕x;
    a1⊕ a2⊕ a3⊕,……,⊕ an=x⊕x=0

如果a1⊕ a2⊕ a3⊕,……,⊕ an=0,无论怎么先手,都会使得a1⊕ a2⊕ a3⊕,……,⊕ an≠0。

  • 证明:假设从第i堆拿走一些石子,原有ai个石子,现有ai’个石子,反证法:如果a1⊕ a2⊕ ai’⊕,……,⊕ an=0,则
    (a1⊕ a2⊕ a3⊕,……,⊕ an)⊕(a1⊕ a2⊕ ai⊕,……,⊕ an)=ai⊕ai’=0,即ai=ai’,矛盾,所以a1⊕ a2⊕ a3⊕,……,⊕ an=0,无论怎么先手,都会使a1⊕ a2⊕ a3⊕,……,⊕ an≠0。
    c++
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int res=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        res^=x;
    }
    if(res==0)puts("No");
    else puts("Yes");
    return 0;
}

java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int res=1;
        for(int i=0;i<n;i++)
        {
            int a=scanner.nextInt();
            res^=a;
        }
        System.out.println((res^1)!=0?"Yes":"No");
    }
}

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/31692.html

先手  石子  后手  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 京圈佛子破戒后,我改嫁京圈纨绔(沈墨渊,白晶晶)
  • 前世被闺蜜害死,重生后我让她从太子妃变疯女苏婉儿,清歌完本_前世被闺蜜害死,重生后我让她从太子妃变疯女(苏婉儿,清歌)
  • 全书浏览七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)_七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)全书结局
  • 今天也没变成昨天(周扬陈默)全书免费_(周扬陈默)今天也没变成昨天后续(周扬陈默)
  • 重生后,秦总非要父以子贵(许沐晴,秦越泽)全书浏览_重生后,秦总非要父以子贵全书浏览
  • 他嫌弃我喝两块钱豆浆上不了台面,我结婚后他又哭又闹全书万照,白青青在线
  • 昭然若梦前尘烬列表_昭然若梦前尘烬(温昭然方池雲)
  • 导师借我股票账号,我倒欠五十万(孟潇潇,宁薇)_导师借我股票账号,我倒欠五十万孟潇潇,宁薇
  • 拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾(周钰泽,蒋清清,思源)全书浏览_拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾全书浏览
  • 我的人生,你已出局(程森凌古楚文)_我的人生,你已出局程森凌古楚文
  • 穿书成病娇女配,睁眼就签下离婚协议书(朱楼)_穿书成病娇女配,睁眼就签下离婚协议书
  • 老婆逼我给白月光捐肾,我死后她悔疯了(宋逸晨沈墨白)全书浏览_老婆逼我给白月光捐肾,我死后她悔疯了全书浏览

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1