主题

主题

 
   

Nim游戏拓展

  • 扯淡

来补坑。

谈及一下Nim游戏的应用。


  • Nim游戏

结论是:

如果石子堆的异或和为0,那么先手必败,反则先手必胜。


  • 小练习

给定n个框,从左到右排列,每个框内初始可能有一些球。两位玩家轮流操作,每次操作可以选择一个框,然后把一个求丢到其左边的一个框内(如果左边没框则不能这么操作)。

求先手必胜/后手必胜的充要条件?

思路:

我们把每个球的位置拿出来,从0开始标号。

发现一次操作就是把这个球的位置减少若干。

那么就转换为了Nim游戏!


  • Topcoder SRM 565-500

按如下方式定义一个游戏:给定 l , r ( l≤r ),定义可重数集 S={x∈Z|l≤x≤r} 。

定义一次操作为选中数集中的某个数 num 然后把它变成一个不等于他自己的因数。

两个玩家轮流操作,没有合法操作(即 S 中所有数都是 1 )的玩家失败。

题目给定两个数 L 和 R ,问有多少种 L≤l≤r≤R 满足 l 和 r 定义的游戏先手必胜。

1≤L≤R≤10^9,R−L≤10^6

思路:

首先不难想到,把一个数字分解质因数,得到x=pai(pi^ci)。接下来我们发现这个数字可以变换的次数就是pai(ci+1)。这就变为了一个Nim游戏。

那么分解质因数以后,问题转换为在[L,R]内有多少子区间[li。。ri]的xor和为0。

那么转换为前缀异或和,用一些高效的数据结构即可。

关于分解质因数的内容,王队长说我们可以用一种筛法。当然Pollard_rho强行卡应该是可以的,不过据说这个筛法可以做到比较小的时间。原理大概是枚举一个数字的倍数的感觉。

反正本人才疏学浅没有用过。


  • 阶梯博弈

给出n+1阶楼梯,编号为0,1...n。现在每一阶阶梯上有一堆石子。可以选择一个阶梯上的若干石子扔到下一个阶梯。

无法操作者为败。

求先手必胜/后手必胜的条件。

思路:

我们发现,编号为偶数的都是无用的。因为对于必胜方,如果对方从偶数第2k阶扔x个石子到第2k+1阶,那么我们可以选择从奇数第2k+1阶扔x个石子到第2k+2阶。

然后第0阶是终止状态。

也就是说,如果一枚石子从奇数阶被扔到了偶数阶,这枚棋子就相当于被永远扔掉了。

那么这就是奇数阶的石子在玩Nim游戏!

所以我们只需要把所有奇数阶的棋子拿出来,然后做xor和。如果xor和为0,则先手必败,反则先手必胜。


  • BZOJ 1115

有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数。

两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件。

谁没有石子可移时输掉游戏。问先手是否必胜。

思路:

首先我们差分一下。令T[i]=A[i]-A[i-1]。那么一次操作相当于在差分数组上把位置p的x枚石子转移到p+1上。

那么就变为了阶梯博弈。


  • BestCoder#90 prob.1002

给定一棵有根树,每个节点上可能有一些石子。2位玩家轮流操作,每次操作可以选择一个节点,取上面的一些石子移动到它的父亲上(如果没有父亲则操作不合法)。

问先手是否必胜。

思路:

拿这棵树的深度当做阶梯即可。


(纯属抄PPT……Orz一下王队长吧)

 
 
评论
 
 
热度(1)