博弈论

巴什博奕：http://acm.hdu.edu.cn/showproblem.php?pid=1846

一堆 n 个物品，两个人，每次最多只能拿走 m 个，先取完胜利；

分析：

1~m 个物品先手胜，m+1个物品后手胜利；

推广： n = (m+1)*r + s，先手只要第一次拿走 s，后手每次也不能拿走（m+1），那么先手只要补上就可以了；也就是说如果 n % (m+1) !=0，先手必胜；

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int c;
 8     scanf("%d",&c);
 9     while(c--) {
10         int n,m;
11         scanf("%d%d",&n,&m);
12         if(n%(m+1))
13             puts("first");
14         else puts("second");
15     }
16     return 0;
17 }

View Code

威佐夫博弈：http://acm.hdu.edu.cn/showproblem.php?pid=1527

两堆物品，每次从一堆中取，或者从两堆中取相同多的物品，谁先取完谁胜利；

分析：

面对（0,0）状态先手输了（专业名词是：奇异状态）；（1,2），（3,5）；

现在给你一个状态，看是否是先手必输状态（奇异状态）；

可以发现，两者的差值 x * 1.618 ((1+sqrt(5))/2）黄金分割 == 较小者；

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int a,b;
 8     while(~scanf("%d%d",&a,&b)) {
 9 
10         int aa = min(a,b);
11         int bb = max(a,b);
12 
13         int tmp = (bb - aa)*((1+sqrt(5))/2);
14         if(tmp==aa)
15             puts("0");
16         else puts("1");
17     }
18 
19     return 0;
20 }

View Code

Nim博弈：http://acm.hdu.edu.cn/showproblem.php?pid=1849

n 堆物品，每次从一堆物品中拿走若干个，谁先取完谁胜利；

分析：

可以通过由必输状态推其父亲结点为必胜状态得到；当然如果 n 较多，每堆物品数量很多，状态数目太多了，就不适合了；将每一堆物品异或，sum 等于 1，先手必胜；

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int m;
 8     while(scanf("%d",&m),m) {
 9         int k;
10         int sum = 0;
11         for(int i=0;i<m;i++)
12         {
13             scanf("%d",&k);
14             sum^=k;
15         }
16 
17         if(sum)
18             puts("Rabbit Win!");
19         else puts("Grass Win!");
20 
21     }
22 
23     return 0;
24 }

View Code

SG函数：http://acm.hdu.edu.cn/showproblem.php?pid=1848

游戏和的SG函数等于各个子游戏SG函数的Nim和；

SG(x) = mex(S)

S：是 x 的后继状态的集合SG函数值；

mex(S) : 是不在 S 集合中的最小非负整数；

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 1010;
 6 
 7 int f[maxn];
 8 int sg[maxn];
 9 bool vis[maxn];
10 
11 int main()
12 {
13     int m,n,p;
14 
15     f[1] = 1;
16     f[2] = 2;
17     for(int i=3;i<maxn;i++)
18         f[i] = f[i-1] + f[i-2];
19 
20     sg[0] = 0;
21     for(int i=1;i<maxn;i++) {
22         memset(vis,0,sizeof(vis));
23 
24         for(int j=1;f[j]<=i;j++)
25             vis[sg[i-f[j]]] = 1;
26 
27         for(int j=0;;j++)
28         {
29             if(!vis[j])
30             {
31                 sg[i] = j;
32                 break;
33             }
34         }
35 
36     }
37 
38 
39     while(scanf("%d%d%d",&m,&n,&p)) {
40         if(m==0&&n==0&&p==0)
41             break;
42         int sum = 0;
43         sum ^=sg[m];
44         sum ^=sg[n];
45         sum ^=sg[p];
46         if(sum)
47             puts("Fibo");
48         else puts("Nacci");
49     }
50     return 0;
51 }

View Code