博客网 >

ZOJ 2507 解题报告
作者:分类:默认分类标签:

http://acm.zju.edu.cn/show_problem.php?pid=2507

题目大意:给定N堆石子的数目,两人轮流取,一次只能从一堆中取,最少取1颗,最多把这堆取完,先取完的人为负,问哪一方会胜。(Nim取子问题的一个变形)

看了ZSU大牛的提示才明白的~~

首先考虑简单情况,当所有的堆都不大于1时,可以根据1的奇偶决定胜负,偶数个1先走方胜。

如果只有一堆大于1,先走方可以选择是把该堆拿完还是剩1个,从而控制剩下的1的奇偶,先走方必胜。

注意只有一堆大于1的情况,一定是一个所谓的非平衡态(参见《组合数学》(Richard.A.Brualdi)第一章),先走方必然想把这个局面留给自己。因此,当初始局面为非平衡态时,他可以始终把平衡态留给对方,对方在被迫不断打破平衡态时,最终必定会把一个只有一堆大于1的非平衡态留给先走方,然后先走方就可以随心所欲了,因此当初始态为非平衡态时,先走必胜。反之,当初始态为平衡态时,先走方必须打破平衡,这样主动权就到了对方手里,先走必败。

到这里可以看出,这题和标准的Nim取子解法很相似,只是在初始情况下所有堆都不大于1时需特殊判断一下。

关于平衡态的判断,也是从ZSU的BBS上学过的,可以用XOR来做,速度极快的说~~~

<< 一个小PHP完工~ / 该学些东西了 >>

专题推荐

不平凡的水果世界

不平凡的水果世界

平凡的水果世界,平凡中的不平凡。 今朝看水果是水果 ,看水果还是水果 ,看水果已不是水果。这境界,谁人可比?在不平凡的水果世界里,仁者见仁,智者见智。

中国春节的那些习俗

中国春节的那些习俗

正月是农历新年的开始,人们往往将它看作是新的一年年运好坏的兆示期。所以,过年的时候“禁忌”特别多。当然,各个地方的风俗习惯不一样,过年的禁忌也是不一样的。

评论
0/200
表情 验证码:

RoBa

  • 文章总数0
  • 画报总数0
  • 画报点击数0
  • 文章点击数0
个人排行
        博文分类
        日期归档