2010年02月05日.sgu153 經典博弈問題 substration game
sgu153:這個問題是經典的博弈論教程<<GAME THEORY>> Thomas S. Ferguson，
1.4 Subtraction Games 中有詳細介紹，就是狀態的逆推。
此書在
http://www.math.ucla.edu/~tom/Game_Theory/Contents.html
上有下載，是作者寫的免費電子書。
本題的關鍵就是找出循環節，然后將n %= len;
進而求出最終的狀態。
下面代碼很挫，基本屬于暴力。
1
2 const int N = 1024;
3 int stat[N];
4 int p[N],m,n;
5
6 bool find(int x)
7 {
8 int i;
9 for (i = 0;i <= m;i++) {
10 if (x - p[i] >= 0 && stat[x-p[i]] == 0) {
11 return true;
12 }
13 }
14 return false;
15 }
16
17 bool repeat(int mod,int offset,int depth)
18 {
19 if (depth == 0) {
20 return true;
21 }
22 int i;
23 for (i = 0;i < mod;i++) {
24 if (stat[i+offset] != stat[i+mod+offset]) {
25 return false;
26 }
27 }
28 return repeat(mod,offset + mod,depth-1);
29 }
30
31 int main()
32 {
33 int i,j,k,testcase,mod = 2;
34 stat[0] = 1, stat[1] = 0, p[0] = 1;
35 scanf("%d",&testcase);
36 while (testcase--) {
37 scanf("%d%d",&n,&m);
38 for (i = 1;i <= m;i++) { scanf("%d",p + i); }
39
40 sort(p,p+m+1);
41 for (i = 2;i <= 1024;i++) {
42 if (find(i)) {
43 stat[i] = 1;
44 }
45 }
46
47 for (i = 2;i <= 20;i++) {
48 if (repeat(i,0,10)) {
49 mod = i;
50 }
51 }
52
53 if (stat[n % mod]) {
54 puts("FIRST PLAYER MUST WIN");
55 }else {
56 puts("SECOND PLAYER MUST WIN");
57 }
58 }
59 return 0;
60 }
61