博弈论入门之nim游戏

nim游戏

nim游戏

有两个顶尖聪明的人在玩游戏,游戏规则是这样的:

有n堆石子,两个人可以从任意一堆石子中拿任意多个石子(不能不拿),没法拿的人失败。问谁会胜利

nim游戏是巴什博奕的升级版(不懂巴什博奕的可以看这里)

它不再是简单的一个状态,因此分析起来也棘手许多

如果说巴什博奕仅仅博弈论的一个引子的话,

nim游戏就差不多算是真正的入门了

博弈分析

面对新的博弈问题,我们按照套路,从简单的情况入手

当只有一堆石子的时候,先手可以全部拿走。先手必胜

当有两堆石子且石子个数相同的时候,先手不论拿多少,后手都可以从另一堆中拿同样多的石子,先手必败,否则先手必胜

当有三堆的时候呢?

当有n堆的时候呢?

这样玩下去却是很繁琐,不过前辈们总结出了一条非常厉害的规律!

定理解析

定理

对于nim游戏,前辈们发现了一条重要的规律!

当\(n\)堆石子的数量异或和等于\(0\)时,先手必胜,否则先手必败

证明

\oplus表示异或运算

nim游戏的必败态我们是知道的,就是当前\(n\)堆石子的数量都为零

设a[i]表示第i堆石子的数量,那么当前局面就是

0 \oplus 0 \oplus 0 \oplus \dots \oplus 0 = 0

  • 对于先手来说,如果当前局面是

a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n = k

那么一定存在某个a_i,它的二进制表示在k最高位上一定是1

我们将a_i \oplus k,这样就变成了

a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n \oplus k = 0

此时先手必胜

  • 对于先手来说,如果当前局面是

a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n = 0

那么我们不可能将某一个\(a_i\)异或一个数字后使得

a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n = 0

此时先手必败

代码

#include<cstdio>
using namespace std;
int a[10001]; 
int main()
{
    int Test;
    scanf("%d",&Test);
    while(Test--)
    {
        int ans=0,N;
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        for(int i=1;i<=N;i++) ans=ans^a[i];
        ans==0?printf("No\n"):printf("Yes\n");
    }
    return 0;
}

题目

临时还没有做太多题目,以后做多了慢慢补吧

题解

  • POJ 1704

估计没几个人能一眼秒吧233

题解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏星流全栈

什么是「设计模式」?

12530
来自专栏AI研习社

如何在 i5 上实现 20 倍的 Python 运行速度?

Intel Distribution for Python 在今年二月进行了更新——英特尔发布了 Update 2 版本。以“加速”为核心的它,相比原生 Pyt...

453130
来自专栏木东居士的专栏

漫谈并发和并行:概述

17240
来自专栏牛客网

【前端面筋】终于等到你!!!

之前一直在牛客刷面筋,今天终于自己也写了一篇,算是秋招的总结吧。希望大家都能顺利拿到自己想要的offer! lz本科妹子,从没有想过要当程序员......无奈非...

425130
来自专栏上善若水

007尝试使用UML图

尝试使用uml图来帮助自己快速的构建稳健的程序 uml对理清自己的思路,应该是很有帮助的了

11520
来自专栏逍遥剑客的游戏开发

Bullet的最小化功能封装

18530
来自专栏我杨某人的青春满是悔恨

如何提高代码品味

写代码虽然大多数时候是个体力活,但不可否认,也需要一点品位。我曾经觉得代码质量很重要,后来写业务写多了,又觉得如果连代码正确都做不到,又谈何代码质量。后来我又醒...

11120
来自专栏奇点大数据

算法之旅(2)——朴素的存取

上次我们说到算法最基本的处理规则和算法在计算机底层所藉由的工作方式。这次我们来说说计算机中最简单的算法,最朴素的数据存取。 也许有的朋友觉得这种问题太底层,简直...

24350
来自专栏牛客网

多篇面经集合,你不容错过的干货!

  5. 写一个单例模式,答主写的是双检查锁单例,问了为什么用 Volatile,synchronize 移到 方法最外面会怎么样?

13620
来自专栏跨界架构师

[译文]Domain Driven Design Reference(三)—— 模型驱动设计的构建模块

  这些模式根据领域驱动设计,广泛地推行了面向对象设计的最佳实践。他们指导决策来提炼模型,并使模型和实现保持一致,每一个都增强了其他的有效性。仔细制定模型元素的...

9920

扫码关注云+社区

领取腾讯云代金券