首页 > 代码库 > [博弈]受限Nim游戏
[博弈]受限Nim游戏
题目大意：有N（1<=N<=100）堆石子，每堆个数给定A1..AN（1<=Ai<=2,147,483,647），现有甲乙两人轮流取石子，由甲开始，每次选一堆，取走一定数目石子，1到Ai的一半取下整，如Ai=5时，可取1或2，Ai=6时，可取1或2或3，但Ai=1不能取。不能取者负，求甲是否获胜。假定每人都采取最优策略。
这是我第一道用sg来做的题目，先贴一个链接，此人对sg的介绍非常好，至少我一遍看懂了，非常感谢。http://blog.163.com/scuqifuguang@126/blog/static/171370086201101711276278/
在说这道题吧，我们可以非常容易地写出sg函数表达式，sg(i)=mex{sg(i-k)} ∈(1,i/2),然后我通过程序发现了一个规律，对于一个数x，它的sg函数值即为
f(x)/2,其中f(x)为x不停地除以2直到它为偶数为止。代码挺短的，贴一个。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 long long ans=0; 5 int T; 6 int n; 7 int main() 8 { 9 scanf("%d",&T);10 while(T--)11 {12 scanf("%d",&n);13 ans=0;14 for(int i=1;i<=n;i++)15 {16 long long x;17 scanf("%I64d",&x);18 while(x&1)x/=2;19 x/=2;20 ans^=x;21 }22 if(ans)puts("Win");else puts("Lose");23 }24 return 0;25 }26
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。