首页 > 代码库 > hdu1850 Being a Good Boy in Spring Festival ,尼姆博弈(Mimm game),Min sum
hdu1850 Being a Good Boy in Spring Festival ,尼姆博弈(Mimm game),Min sum
题意:
桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);
两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
题解:
尼姆博奕(Nimm Game)
先求所有堆的 Nim-sum = N1 ^ N2 ^ ... NM
然后
res =Nim-sum ^ Ni
如果 res < Ni, 则先手玩家只要第一步从Ni堆中取走Ni-res个, 则剩下的局面Nim-sum = 0,
即为剩下的局面为必败态。则这就一种取胜的方案。
对于每个堆的操作至多只有一种方法可以导败必败点(Nim-sum = 0)
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[200]; int main() { int n; while(~scanf("%d", &n)&&n) { int sum = 0; for(int i=0; i<n; ++i) { scanf("%d", &a[i]); sum ^= a[i]; } int ans = 0; for(int i=0; i<n; ++i) if(a[i] > (sum^a[i]) ) ans++; printf("%d\n", ans); } return 0; }<span style="font-family:Arial, Helvetica, sans-serif;"><span style="white-space: normal;"> </span></span>
hdu1850 Being a Good Boy in Spring Festival ,尼姆博弈(Mimm game),Min sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。