北京地区赛B题
一个博弈题。
题目描述如下：有一堆N个石子，两个玩家轮流从这堆石子中取石子。第一个玩家第一次只能取最多N-1个石子。以后，每个玩家取的石子数最多为对方上一次取得K倍，最少取一个。最后一次取得玩家为胜。问，第一个玩家第一次最少取几个石子，可以保证取胜。
看到题的第一感觉，就是博弈题。但是，以前基本没有接触过博弈题，无从下手。于是从网上现找了本博弈论的电子书，英文版的，现学。研究半天fabonacci nim游戏后，没看出名堂来。于是自己模拟着画出了前几个状态，便有了些启示。
我们可以求出一些必败点。可以有这么一个特性，假如一个点到其前面的第一个必败点，它们之间的差距与k的乘积会小于必败点的数值的话，这个点为非必败点。如果乘积大于等于必败点的值，则判断，若它们的差值不是一个必败点的话，也就是说可以从这个点走奇数步到必败点，这时候这个点无疑也是非必败点。
现在的结论也就这些，至于具体的步数，还有待研究。。。
~Charlie
Tags: fabonacci nim, 博弈
This entry was posted by Charlie at 10:23 pm and is filed under ACM Life.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.