hdu 1848 博弈之SG函数的使用

题目地址：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

<code>#include &lt;stdio.h&gt;</code>

<code>#include &lt;stdlib.h&gt;</code>

<code>#include &lt;string.h&gt;</code>

<code>int</code> <code>f[1005],sg[1005],hash[1005];</code>

<code>void</code>

<code>GetSg(</code><code>int</code>

<code>n)</code>

<code>{</code>

<code>      </code><code>int</code>

<code>i,j;</code>

<code>      </code><code>memset</code><code>(sg,0,</code><code>sizeof</code><code>(sg));</code>

<code>      </code><code>for</code><code>(i=1;i&lt;=n;i++)</code>

<code>      </code><code>{</code>

<code>            </code><code>memset</code><code>(hash,0,</code><code>sizeof</code><code>(hash));</code>

<code>            </code><code>for</code><code>(j=1;f[j]&lt;=i;j++)</code>

<code>            </code><code>{</code>

<code>                 </code><code>hash[sg[i-f[j]]]=1;</code>

<code>            </code><code>}</code>

<code>            </code><code>for</code><code>(j=0;j&lt;=n;j++)</code>

<code>                 </code><code>if</code><code>(hash[j]==0)</code>

<code>                 </code><code>{</code>

<code>                     </code><code>sg[i]=j;</code>

<code>                     </code><code>break</code><code>;</code>

<code>                 </code><code>}</code>

<code>            </code><code>}</code><code>//printf("%d",sg[n]);</code>

<code>      </code><code>}</code>

<code>}</code>

<code>int</code>

<code>main()</code>

<code>     </code><code>int</code>

<code>i,j,m,n,p;</code>

<code>     </code><code>f[0]=1;f[1]=1;</code>

<code>     </code><code>for</code><code>(i=2;i&lt;=16;i++)</code>

<code>     </code><code>{</code>

<code>          </code><code>f[i]=f[i-2]+f[i-1];</code>

<code>     </code><code>}</code>

<code>     </code><code>GetSg(1001);</code>

<code>     </code><code>while</code><code>(</code><code>scanf</code><code>(</code><code>"%d%d%d"</code><code>,&amp;m,&amp;n,&amp;p)!=EOF&amp;&amp;m||n||p)</code>

<code>             </code><code>if</code><code>((sg[m]^sg[n]^sg[p]))</code>

<code>             </code><code>{</code>

<code>                  </code><code>printf</code><code>(</code><code>"Fibo\n"</code><code>);</code>

<code>             </code><code>}</code>

<code>             </code><code>else</code>

<code>                  </code><code>printf</code><code>(</code><code>"Nacci\n"</code><code>);</code>

<code>     </code><code>return</code>

<code>0;</code>

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

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

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

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

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

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

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