hiho一下 第四十五周 博弈游戏·Nim游戏·二(转成NIm)
2024-08-24 04:38:26
Alice和Bob这一次准备玩一个关于硬币的游戏:
N枚硬币排成一列,有的正面朝上,有的背面朝上,从左到右依次编号为1..N。现在两人轮流翻硬币,每次只能将一枚正面朝上的硬币翻过来,并且可以随自己的意愿,在一枚硬币翻转后决定要不要将该硬币左边的任意一枚硬币也翻一次(正面翻到背面或背面翻到正面)。翻最后一枚正面向上的硬币的人获胜。同样的,这次游戏里面Alice仍然先手,两人均采取最优的策略,对于给定的初始局面,Alice会获胜还是Bob会获胜?
题意:
要使得所有硬币背面向上。每次只能反转一个正面向上的硬币到背面向上,同时可选择对该位置左边的其中一个硬币进行反转。
思路:
官网已经很详细说明解法,但是思路可能不是很顺,多看几遍应该就行了。主要就是(1)拆成单个正面的情况,转成Nim(2)考虑是否会有与Nim规则冲突的地方。
关于赢家如何维持必赢局面?
无论对方取走多少石子,赢家只要取走同数量的石子即可,即”抵消“!因为两者的异或结果为0。若是在刚开局时,对方并还没有行动过,那么赢家可以取走一堆比较特殊的石子,只要使得其他的异或结果为0就保持了每次留赢的局面给自己。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int a[N];
int main()
{
//freopen("input.txt","r",stdin);
int n;
string s;
while(cin>>n)
{
cin>>s;
int j=;
for(int i=; i<n; i++) //拆成单个正面情况
{
if(s[i]=='H')
a[j++]=i+;
}
for(int i=; i<j; i++)//异或,计算结果
a[]^=a[i];
if(a[])//不为0
cout<<"Alice"<<endl;
else
cout<<"Bob"<<endl;
}
return ;
}
AC代码
最新文章
- 【Kindle】pdf转mobi适合kindle查看格式
- 安装Python算法库
- poj 1112
- Codeforce Round #226 Div2
- 错误:Error:未定义标识符";_TCHAR";
- Integer的缓存和自动拆装箱
- Delphi EurekaLog 调试内存泄露方法
- 《奇思妙想》在JavaScript语言中floor和round方法在某种随机分配场景下对分配区间的公平性!!!
- C#中System.DateTime.Now.ToString()用法
- 页面第一次加载,JS没有效果,刷新一下就好了
- Mac android studio 一直卡在Gradle:Build Running的解决办法
- python爬虫训练——正则表达式+BeautifulSoup爬图片
- BZOJ 2879 [Noi2012]美食节 | 费用流 动态开点
- Struts2(一)
- [BZOJ1131/POI2008]Sta树的深度
- 文献综述六:基于JS 技术的电子商品管理系统设计及实现
- win10实现移动热点共享WIFI
- Forward链、Input链和Output链的区别
- HDU 1394.Minimum Inversion Number-最小逆序数-完全版线段树(单点增减、区间求和)
- Sql Server 表分区(转)
热门文章
- SLAM细碎内容积累_来自各种技术交流群_持续更新
- ListView Item 里多种点击事件的用法
- MVC+NHibernate笔记
- 在GitHub上上传项目(转载)
- Lightoj1007【欧拉函数-素数表】
- MySQL (case when then else end)和常用函数用法
- JQuery Easyui/TopJUI 基本树形表格的创建
- 解决import sun.misc.BASE64Decoder; import sun.misc.BASE64Encoder;报错的问题
- docker镜像创建
- NSwag生成客户端调用代码