首页 > 代码库 > hdu 1848 博弈之SG函数的使用

hdu 1848 博弈之SG函数的使用

2024-07-04 19:26:00   222人阅读

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1848

题目简单描述为：

1、  这是一个二人游戏;
2、  一共有3堆石子，数量分别是m, n, p个；
3、  两人轮流走;
4、  每走一步可以选择任意一堆石子，然后取走f个；
5、  f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量）；
6、  最先取光所有石子的人为胜者；

假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。

代码为：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
 
int f[1005],sg[1005],hash[1005];
void GetSg(int n)
{
      int i,j;
      memset(sg,0,sizeof(sg));
      for(i=1;i<=n;i++)
      {
            memset(hash,0,sizeof(hash));
            for(j=1;f[j]<=i;j++)
            {
                 hash[sg[i-f[j]]]=1;
            }
            for(j=0;j<=n;j++)
            {
                 if(hash[j]==0)
                 {
                     sg[i]=j;
                     break;
                 }
            }//printf("%d",sg[n]);
      }
}
 
int main()
{
     int i,j,m,n,p;
     f[0]=1;f[1]=1;
     for(i=2;i<=16;i++)
     {
          f[i]=f[i-2]+f[i-1];
     }
     GetSg(1001);
     while(scanf("%d%d%d",&m,&n,&p)!=EOF&&m||n||p)
     {
             if((sg[m]^sg[n]^sg[p]))
             {
                  printf("Fibo\n");
             }
             else
             {
                  printf("Nacci\n");
             }
     }
     return 0;
}

　　===============================================================================================

看了一星期的SG函数，现在才算懂那么一点点，看了张一飞大神的论文，果然写的很好，堪称经典之作

接下来看了：http://www.cnblogs.com/frog112111/p/3199780.html这里的博客，SG模板，又看了好长时

间才看懂，程序的巧妙之处，看许多次才能领略

我简单说一下：y是x的后继，说的是x下一步可以到达的状态y，f[] 保存的是取石子的规则，可以取的种类

hash[]数组保存所有后继值，sg[]数组保存最小的不属于这个集合的非负整数

如果你看不懂以上所说，那就取百度下张一飞大神的论文，一点点耐心看完！

 


联系
我们