hdu 1850 Being a Good Boy in Spring Festival (nim游戏问必胜方案数,sg函数)

hdu1850题目链接
题意:n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。
思路:sg函数。。对于方案数,可以用nim游戏的结论。

未命名。设异或和为sum..那么统计满足 a[i]^sum<a[i]的个数就是第一步能走的方案数。

以[……]

Read more

nim游戏以及证明过程

参考资料  (后面的证明写错了,差评,不要看,看图就好了)

 

  1. 题目1:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,

 

可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

 

题目2:今有若干堆火柴,两人依[……]

Read more

bestcoder #56 div 2 C Clarke and puzzle (nim游戏 树状数组)

比赛的时候没过.还以为是树状数组写残了.
但实际上是有自己不知道的东西.
这种博弈叫 nim游戏
所以这是一个二维的nim游戏.
nim游戏的性质是xor 和为0必败,否则必胜.
xor和也有前缀和性质,所以可以用树状数组维护.

[crayon-5a8f04bfb6c4416860[……]

Read more