Sicily 1305 Who’s Winner? (SOJ 1305)「Nim问题」

5.00 avg. rating (97% score) - 1 vote
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/139

原题地址:点击打开链接

我以前最烦这种策略、博弈问题,因为总是觉得无章可循,要解题只能依靠灵光一闪,但是看了《编程之美》这本书后(绝对是好书,我对其评价如下哈哈:《推荐一本书》),看到这题我就大致想出解法了。

——————正文——————

我个人认为这也是Nim问题的一种,这一题换一种叙述方式可以是,对于某一范围的石头,每次可以取走若干,使其变为原来的多少分之1,最终剩下多少个石头就谁获胜。

对这题的求解过程比较诡异,因为我一开始看错题,以为仅仅从2和9两个数字中选1个,后来才发现是2~9,神奇的是,我发现就算看错了题,做法也是不变的···

好了,说说这题的思路,套用《编程之美》这本书里面解这类题的思想,可以划分“安全区”的概念,安全区就是(通常针对玩家1)玩家在里面就必定不会输的区域。

举个例子,对于玩家来说:

1 n~无穷是安全区,因为走到这个区域里面,玩家必定胜利

2 n/9(上取整)~n-1 是危险区,玩家一旦走到这个区域里面,另外一个玩家下一次动作就会胜利

3 我们假设2中k=n/9(上取整),kk=n-1,进一步地,k/2(上取整)~k-1是安全区….

按照上面这样递推,有一个问题,为什么有时候是除以2,有时候是除以9?

这样思考——当玩家要到达安全区,那么必定有其对手在危险区,所以从当前的安全区逆推危险区的范围时,应该使用除以9(思考为什么);而怎么样才能令到对手会走到危险区上?只有自己走到某一个区域,而在这个区域上面,无论对手下一步选择什么数字,都会走到危险区上面,当前自己所在的区域就是安全区,所以安全区内的数字,应该保证其乘以2~9中任何数字,都会进入危险区的范围。

简而言之,在安全区的人,可以永远保证自己在安全区,而在危险区的人,用于会在危险区。所以我们只需要知道Susan或Nic一开始在什么区就可以了。

上面是最难理解的···顺带说一句,今天校队4+2补选赛砸了,哎。

继续。

由于Nic从1开始乘,所以我们选择Susan作为游戏的first player,然后她的数字是1 。然后按照刚才的方法,看看递推下来,区间在包含1的时候,当前的区间是危险区还是安全区就可以知道SUSAN赢还是输了。

后来发现要考虑一种特殊情况:如果n<=9,那么就直接输出Nic胜利,否则就按上面的方法计算。

可能我解释得不好,各位看代码吧,如下:

#include<stdio.h>
#include<iostream>
using namespace std;
long long n;
long long lb,ub;  //当前区间的左边界和右边界 
bool w;           //w=true则当前区间是安全区 
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%lld",&n)!=EOF)
    {
      if(n<=9)
      {
        printf("Nic wins.\n");
        continue;
      }
                                
      lb=n; ub=2*n;
      w=true;
      while(!(lb<=1 && ub>=1))
      {
        //printf("%lld %lld\n",lb,ub);
        ub=lb-1;
        long long tmp=w?9:2;
        long long tmp2=lb/tmp;
        for(;tmp2*tmp<lb;++tmp2)
        {}
        lb=tmp2;
        w=(!w);
      }
      if(w)
        printf("Susan wins.\n");
      else
        printf("Nic wins.\n");
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注