博弈--尼姆博弈
2020-05-03 16:00:56来源:博客园 阅读 ()
博弈--尼姆博弈
今天我们来聊一聊另一种博弈--尼姆博弈,这一种博弈可以说是巴什博弈的一种变体,巴什博弈中“石子”的堆数为1堆,而在利姆博弈中“石子”的堆数为n堆,还有在尼姆博弈中取石子的规则也发生了变化,前一种博弈中取石子的数量限定在[1,L],而后一种取石子的数量可以为任意数(但不能不取,而且还不能超过这一堆石子的总数),同样也是两人轮流来取,先取完者获胜。
下面我们进行一下分析:
(1) 先假设只有两堆石子,当两者数量相同的时候,先手必败(先手从一堆中取a个石子,后手模仿先手从另一堆也取a个,最后一定是先手败);当两者数量不相等时,先手可以通过取石子将两堆石子变为的数量变为一样,这样,后手就面临必败态了。
综合来看的话:当谁面临“两堆石子的数量相等”这一状态时,谁就必败。
(2) 现在我们将情况推广到普通状态,我们先假设存在两堆石子a=7,b=5。这是两堆数量不同的石子堆,通过二进制拆分可以将他们化为:111 101,也就是(4+2+1)(4+1),我们现在可以将其视为5堆石子,其中有两堆数量为4,两堆数量为1的石子,也就是说,谁面临这种情况,谁就必败。而最后一堆谁将它一次性全部拿走,谁就是赢家。而通过二进制拆分可以将两堆数量分别为4、1的石堆归零不计。而通过异或这一操作正好可以达到这一要求。
由上得到结论:对每一堆石子的数量进行异或,最终的值为0时(尼姆和),先手必败,反之,先手必胜。
典型例题:
Matches Game
题意:n堆石子,两个人轮流取,先取完者获胜。
题解:尼姆博弈的模板,直接套用。
代码:
#include<iostream> #include<algorithm> #define ll long long using namespace std; int main() { ll n,t; while(cin>>n) { ll sum=0; cin>>sum; for(int i=1; i<n; i++) { cin>>t; sum=sum^t; } if(sum==0) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }
相似题目推荐 :HDU - 2176 HDU-1850
原文链接:https://www.cnblogs.com/blogxsc/p/12822697.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:前缀和
- CF1215DTicketGame——(博弈) 2020-04-25
- 博弈--巴什博弈 2020-04-24
- 博弈论入门 Bash 、Nim 、Wythoff's Game结论及c++ 2019-01-23
- HDU6312 Game (多校第二场1004) 简单博弈 2018-09-18
- codechef Table Game(博弈) 2018-09-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash