搜索

poj2068

每轮最多取子数目不同的单堆NIM
胜败态搜索

poj1082

日历上的博弈
可以移动到下一天或者下个月的这一天

poj2311

NM 的方格,最先剪下一个11的方格的人赢

搜索剪线的位置,合并两个后继两个状态的sg
从2开始剪,因为1的时候必败

模型

uva12499

有n堆石子,每堆最多加到l,且要保持从左向右不降的关系

阶梯NIM

每堆 l - a[i],然后对差值进行阶梯NIM,游戏顺序是从左向右的

规律

cf124-A

矩形内放圆,不能放的输

若先手可以放,先手必胜: 第一个放中间,其余的放后手的对称位置

  • 图形内放图形问题基本上都可以秒杀了…

poj1740

楼教主的男人八题之一…

n堆石子,每次选一堆,移走至少一个石子
其余的可以随意分配到其他堆,或者不变
最后不能取的人输

如果对于k个石子的堆,有另一个堆石子数目也为k与之配对
(即所有数目的石子堆数都为偶数
那么无论先手如何操作,后手总可以复制先手的操作使得状态不变
这种情况下先手必败

若存在堆的数目为奇数个(假设递增排列,不考虑已经配对的堆)

  • 1个: x 先手必胜
  • 2个: x y 从y中取y-x个,状态变为x x
  • 3个: x y z 从z中取y-x个,其余的取走,状态变为y y
  • 2k+1个: 取最后一个,凑出k组两两相同的堆 (我们发现前2k个的差的和总小于2k+1个
  • 2k个: 最后一个和第一个配对,其余的分配到其他堆上 (即在前面加一个数目为0的堆

poj2348

两个数,每次从大的数中减去较小的数的倍数,不能减的人输

我是直接搜的…注意减的时后从大到小减(否则过不了),这么更容易到达最终状态

然而正解是,假定 a > b:

  • 若 a%b=0,先手必胜
  • 若 a > 2b,先手必胜,因为状态可转化为(a,a%b) 和 (a,a%b+b) 这两种状态是相邻的
    因此一定有一种状态为必败态
  • 若 a < 2b,状态转移到(b,a-b)

hdu5795

NIM 加了个规则: 个数 > 3的堆可以分成不为0的三份