CodeForces 347C Alice and Bob

题意

两个人互相玩,他们先搞一个集合,里面几个不同的数,接下来随便挑俩作差,如果差的绝对值集合里没有,就给这个差的绝对值加进去,直到集合加不进去值为止,没招的那位就跪了。

思路

写几个数模拟一下就会发现,游戏结束时,集合里面是所有的初始几个值的最大公约数的倍数,举个例子init={2,6,8},gcd=2,final={2,4,6,8},利用这个规律我们就可以知道最终集合有几个元素,最终元素个数减去初始元素个数就是这场比赛将在多少手之后结束,接下来判断奇偶就可以判断谁赢了。

接下来上代码

 

HDU 1730 Northcott Game

我把做错了的也发出来,一种典型的做错了的思路就是:先查Tom和Jerry的初始位置有空隙的行的个数,如果是奇数就是一种情况偶数另外一种情况,这个是不正确的。

正确的思路:我们可以把问题转化为没行空隙的大小就是每堆石子的个数,双方每轮任选一堆,取少则为1多则任意大枚石子,先取完获胜,这就是典型的Nim博弈。所以把每一行空隙大小(abs(a-b)-1)挨个xor,然后看看是不是0就行了。

Scroll to top