高僧斗法(博弈-Nim博弈)

简介: 古时丧葬活动中经常请高僧做法事。仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。 节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人,其它任意。(如图1所示) 两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。两个小和尚也不能站在同一台阶,也不能向低级台阶移动。 两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。轮到哪个法师指挥时

❓问题描述

问题 1459: [蓝桥杯][2013年第四届真题]高僧斗法

时间限制: 1Sec 内存限制: 128MB 提交: 40 解决: 7

题目描述

古时丧葬活动中经常请高僧做法事。仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。 节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人,其它任意。(如图1所示) 两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。两个小和尚也不能站在同一台阶,也不能向低级台阶移动。 两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。轮到哪个法师指挥时无法继续移动,则游戏结束,该法师认输。 对于已知的台阶数和小和尚的分布位置,请你计算先发指令的法师该如何决策才能保证胜出。  

输入

输入数据为一行用空格分开的N个整数,表示小和尚的位置。台阶序号从1算起,所以最后一个小和尚的位置即是台阶的总数。(N< 100,  台阶总数< 1000)

输出

输出为一行用空格分开的两个整数:  A  B,  表示把A位置的小和尚移动到B位置。若有多个解,输出A值较小的解,若无解则输出-1。

样例输入

1  5  9

c样例输出

1 4

💡思路

这是一道经典的阶梯Nim博弈问题,想解决这道题 首先要知道Nim博弈(如果知道就直接看代码吧), Nim博弈就是说,给你几堆小石子 ,让两个玩家分别在这几堆小石子中取出石子(可以将某堆石子全部取出 也可以在某堆中只取一个小石子,当然是不可能不取的,不然还玩撒)。谁取到最后 ,没有石子取就输了。

比如 有 3 堆石子 ,每堆分别为 2 3 4个小石子,如下图所示  

网络异常,图片无法展示
|

玩游戏都想赢 ,所以 如何取尤为重要,方案有很多,想快速知道如果我方先手 是赢 还是输,直接就用Nim 研究过的成果。

Nim 的做法 就是 将  2 3 4 都转化为2进制再 异或 得出结果,如果结果是非0 那么先手必定赢 如果结果为0 那么先手必输(前提,玩游戏的都想赢 且都很聪明)

网络异常,图片无法展示
|

  可以看到异或后得到的结果是非0 则先手必胜, 先手遇到如此局面肯定会想办法 将它 变成0 这里先手在个数为4的一堆中取出3个。这堆就变成1个 整个局面的结果 就变成0,那么后手进行操作的话,无论操作 哪一堆,在哪堆中拿多少个石子,看看下图对不对。 肯定会破坏这种局面,让结果变为非0,比如后手在为3堆一堆取走3,

网络异常,图片无法展示
|

比如后手在为3堆一堆取走3,如下图

网络异常,图片无法展示
|

现在又到该先手取石子了,这个时候先手肯定要把 2个石子的一堆取出1个来,还剩1个,如图所示

网络异常,图片无法展示
|

现在又轮到 后手去取石子,现在一眼就可以看出  先手必赢了吧,  后手根据规则 只能拿走一个,然后轮到先手 拿了最后一个,后手就没得办法取 ,游戏就结束了。

现在回过头来 看阶梯Nim博弈问题。 只需要将 阶梯Nim博弈问题转换为Nim博弈问题即可,做如下转换,每两个和尚之间看做一堆,比如 和尚分别站 1  3   5   8   那么可以转换为3堆,分别为 1  1  2,再取异或 就可以知道 先手是否必赢,具体实现可以看代码。(注意; 如果移动了一个小和尚 除了边界 ,会影响相邻两堆的情况,看代码注释)

网络异常,图片无法展示
|

AC代码

#include<iostream>
#define N 102
using namespace std; 
int main(){
  int a[N],b[N];
    int n = 0,i,j,k,sum = 0;
      while(cin>>a[n])n++;//存储又有多少个小和尚 
     for(i=1; i<n; i++)b[i-1] = a[i] - a[i-1] - 1;// 进行Nim博弈的转换 
       for(i=0; i<n-1; i+=2) sum ^= b[i];//进行异或 
    if(sum==0)cout<<-1<<endl;//若开始局面为0 则必输 
    else//若非0 则必赢,因此 需要找到第一步 将局面变为0 的步骤 
    {
        for(i=0; i<n-1; ++i)//枚举移动第i堆  使得剩下的局面异或等于0,
            for(j=1; a[i]+j<a[i+1]; ++j) {//枚举可以移动的步数  保证 前项移动j 步后 不会超过后项 
          b[i] -= j;//拿走 j个 ,这里代表 前一个向上移动j步 
                if(i!=0)b[i-1] += j;//它的后一堆b[i]向取走了j个,那莫前一堆 b[i-1] 则要增加j个 第一堆除外 
            sum = 0;
            for(k=0; k<n-1; k+=2) sum ^= b[k];//重新计算局面, 
       if(sum==0) {cout<<a[i]<<" "<<a[i]+j<<endl; break;}//若变成0  则后手必败,先手必赢。跳出即可; 
            b[i] += j;//回溯 这不是必赢的操作 
            if(i!=0) b[i-1] -= j; 
          }
    }
    return 0;   
}

题目链接:蓝桥杯2013年第四届真题-高僧斗法 - C语言网

目录
相关文章
|
机器学习/深度学习 人工智能 测试技术
Meta无限长文本大模型来了:参数仅7B,已开源
【4月更文挑战第26天】Meta 研究团队推出7亿参数的MEGALODON,这是一个专为无限长文本序列建模设计的神经网络架构。通过复数指数移动平均(CEMA)和时间步归一化层等技术创新,MEGALODON在效率和准确性上超越Transformer,且在多种基准测试中表现优秀。源代码已开源,为长序列建模提供新工具,但面临资源限制和处理极端长度序列的挑战。[论文链接](https://arxiv.org/pdf/2404.08801.pdf)
302 3
|
4月前
|
安全 Linux 开发工具
【Azure Function】分享把Function App从.NET 6.0升级到.NET 8.0 Isolated的步骤
本文介绍了将Azure Function App从.NET 6.0升级到.NET 8.0 Isolated的步骤。.NET 6.0作为长期支持版本,生命周期至2024年11月结束。为确保持续支持,建议升级至更新版本。升级步骤包括安装.NET 8 SDK、更新Azure Functions Core Tools、修改项目文件目标框架为net8.0、更新兼容的NuGet包、本地测试以及重新发布到Azure。更多详细信息可参考官方文档。
193 9
|
存储 JavaScript 前端开发
Vue 3的响应式系统是如何工作的呢
【9月更文挑战第3天】Vue 3的响应式系统是如何工作的呢
332 4
|
存储 关系型数据库 数据库
云数据库如何确保数据的安全性和可靠性?
云数据库如何确保数据的安全性和可靠性?
382 0
|
存储 机器学习/深度学习 分布式计算
【DSW Gallery】COMMON_IO使用指南
COMMON_IO模块提供了TableReader和TableWriter两个接口,使用TableReader可以读取ODPS Table中的数据,使用TableWriter可以将数据写入ODPS Table。
【DSW Gallery】COMMON_IO使用指南
|
机器学习/深度学习 分布式计算 并行计算
当 Mars 遇上 RAPIDS:用 GPU 以并行的方式加速数据科学
在数据科学世界,Python 是一个不可忽视的存在,且有愈演愈烈之势。而其中主要的使用工具,包括 Numpy、Pandas 和 Scikit-learn 等。 Mars 在 MaxCompute 团队内部诞生,它的主要目标就是让 Numpy、pandas 和 scikit-learn 等数据科学的库能够并行和分布式执行,支持通过 RAPIDS 平台用 GPU 加速数据科学。
2282 0
当 Mars 遇上 RAPIDS:用 GPU 以并行的方式加速数据科学
|
SQL Web App开发 XML
企望制造ERP系统存在远程命令执行漏洞
企望制造 ERP comboxstore.action接口权限设置不当,默认的配置可执行任意SQL语句,利用xp_cmdshell函数可远程执行命令,未经认证的攻击者可通过该漏洞获取服务器权限。
465 1
|
存储 弹性计算 固态存储
阿里云服务器是如何收费的?阿里云服务器各收费项目收费标准参考
阿里云服务器收费标准包括实例价格、预留实例券价格、专有宿主机、块存储价格、存储容量单位包、带宽价格、快照服务价格等,云服务器价格主要由云服务器配置费用+磁盘价格+网络宽带价格,配置指的是云服务器的实例规格和cpu与内存配置,本文为大家分享一下2023年阿里云服务器所有收费项目的最新收费标准,以表格形式展示给大家,以供参考。
阿里云服务器是如何收费的?阿里云服务器各收费项目收费标准参考
|
前端开发
Bootstrap纯CSS3箭头按钮样式
Bootstrap纯CSS3箭头按钮样式
289 0
|
关系型数据库 PostgreSQL
postgreSQL获取随机数ID
postgreSQL获取随机数ID
293 0

热门文章

最新文章