[Nim博弈]hdu 1850 Being a Good Boy in Spring Festival
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1850
Being a Good Boy in Spring Festival
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4053 Accepted Submission(s): 2394
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧
陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐
如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢~
下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负,我只想问大家:
——“先手的人如果想赢,第一步有几种选择呢?”
3 5 7 9 0
1
题目意思:
有M堆扑克,每堆有Ni张,两个人轮流拿可以拿一堆中的任意张,最后不能拿的人输。求先拿者获胜的拿法。
解题思路:
Nim博弈。
记n1^n2^n3..^n[m]=x
显然若x=0,则该局势为奇异局势,必输。
如果把ni变成x^ni,则n1^n2^...^n[i-1]^n[i+1]^...^n[m]^x^ni=0,为奇异局势。显然如果ni>x^ni,如果能ni堆中拿走ni-x^ni张牌,则一定会获胜。
所以只用统计ni中比x^ni大于的个数,结果就是先拿者获胜的种数。
代码:
//#include<CSpreadSheet.h> #include<iostream> #include<cmath> #include<cstdio> #include<sstream> #include<cstdlib> #include<string> #include<string.h> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #include<bitset> #include<cmath> #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define ll __int64 #define LL long long #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #define M 1000000007 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 1100000 int hp[Maxn]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; while(scanf("%d",&n)&&n) { int ans=0,sum=0; for(int i=1;i<=n;i++) { scanf("%d",&hp[i]); sum^=hp[i]; } for(int i=1;i<=n;i++) if(hp[i]>(sum^hp[i])) //拿走hp[i]-(sum^hp[i])个,是一种赢法 ans++; printf("%d\n",ans); } return 0; }
[Nim博弈]hdu 1850 Being a Good Boy in Spring Festival,古老的榕树,5-wow.com
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。