专题训练之博弈

推荐几篇文章：https://blog.csdn.net/strangedbly/article/details/51137432（SG函数详细介绍）

https://blog.csdn.net/shahdza/article/details/7832997 博弈题集

SG函数解题模型：

1.把原游戏分解成多个独立的子游戏，则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。

即sg(G)=sg(G1)^sg(G2)^...^sg(Gn)。

2.分别考虑没一个子游戏，计算其SG值。

SG值的计算方法：（重点）

A.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);

　 B.可选步数为任意步，SG(x) = x;

　 C.可选步数为一系列不连续的数，用模板计算。

模板：假设起点为n，总共有m种移动步数可以选择

1.打表（首选打表预处理）

思路：对于一个位置，找到其所有的后继点的SG值有哪些，该位置的SG值即为不等于其后继点的SG值的最小非负整数

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1005;
 6 const int maxm=105;
 7 int f[maxm],sg[maxn]; //f表示移动步数,sg表示每个位置的sg值 
 8 bool vis[maxn]; //vis表示对于某个位置来说，其后继节点的sg值有哪些 
 9 int n,m;
10 
11 void get_sg()
12 {
13     int i,j;
14     memset(sg,0,sizeof(sg));
15     for ( i=1;i<=n;i++ ) {
16         memset(vis,false,sizeof(vis));
17         for ( j=1;f[j]<=i&&j<=m;j++ ) vis[sg[i-f[j]]]=true; //对后继节点所处的位置标记为true 
18         for ( j=0;j<=i;j++ ) { //该位置的sg值 
19             if ( !vis[j] ) {
20                 sg[i]=j;
21                 break;
22             } 
23         }
24     }
25 }

打表求SG值

2.dfs

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1005;
 6 const int maxm=105; 
 7 int f[maxn],sg[maxn],n,m;  //sg除了位置0初始化为0外，其余点初始化为-1 
 8 bool vis[maxn];
 9 
10 int dfs(int x)
11 {
12     if ( sg[x]!=-1 ) return sg[x];
13     memset(vis,false,sizeof(vis));
14     for ( int i=1;i<=m;i++ ) {
15         if ( x>f[i] ) {
16             int y=dfs(x-f[i]);
17             vis[y]=true;
18         }
19     }
20     for ( int i=0;i<=n;i++ ) {
21         if ( !vis[i] ) return sg[x]=i;
22     }
23 }

DFS求SG值

打表找规律求SG值：这类题目可以通过暴力求得小范围的SG值，再通过找规律得到SG值取值的规律

1.（HDOJ2897）http://acm.hdu.edu.cn/showproblem.php?pid=2897

分析：bash博弈变形，一般的bash博弈是从[1,m]个数中取一个，判断先手是否获胜只用看n%(1+m)是否为0。此题是从[p,q],当i<=p时都为必败点，当p<i<=q时都为必胜点。而原先必定是以（p+q）为周期的。所以只需对n%(p+q)，若结果为0或者结果大于p则为输出WIN,否则输出LOST

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n,q,p;
 9     while ( scanf("%d%d%d",&n,&p,&q)!=EOF ) {
10         n%=(p+q);
11         if ( n>p || n==0 ) printf("WIN
");
12         else printf("LOST
");
13     }
14     return 0;
15 }

HDOJ2897

2.（HDOJ3032）http://acm.hdu.edu.cn/showproblem.php?pid=3032

题意：有n堆，每堆有s[i]个，每次可以从一堆中取走[1,a[i]]个或者将这堆分成任意数量的两堆，Alice先，求最后谁获胜

分析：暴力打表得sg+找规律。得到sg( 4k+1 ) = 4k+1； sg( 4k+2 ) = 4k+2； sg( 4k+3 ) = 4k+4； sg( 4k+4 ) = 4k+3；最后再将这n个sg值异或和即可。

规律的正确性证明：http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=29685&messageid=1&deep=0

变形：可以分成任意数量的三堆

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 int main()
 8 {
 9     ll T,n,i,j,k,x,y,z,ans;
10     scanf("%lld",&T);
11     while ( T-- ) {
12         scanf("%lld",&n);
13         ans=0;
14         for ( i=1;i<=n;i++ ) {
15             scanf("%lld",&x);
16             if ( x%4==3 ) x++;
17             else if ( x%4==0 ) x--;
18             ans^=x;
19         }
20         if ( ans!=0 ) printf("Alice
");
21         else printf("Bob
");
22     }
23     return 0;
24 }

HDOJ3032

3.（HDOJ3537）http://acm.hdu.edu.cn/showproblem.php?pid=3537（翻硬币模型）

翻硬币游戏

一般的翻硬币游戏的规则是这样的：

N 枚硬币排成一排，有的正面朝上，有的反面朝上。我们从左开始对硬币按1 到N 编号。

第一，游戏者根据某些约束翻硬币，但他所翻动的硬币中，最右边那个硬币的必须是从正面翻到反面。例如，只能翻3个硬币的情况，那么第三个硬币必须是从正面翻到反面。如果局面是正正反，那就不能翻硬币了，因为第三个是反的。

第二，谁不能翻谁输。有这样的结论：局面的SG 值为局面中每个正面朝上的棋子单一存在时的SG 值的异或和。即一个有k个硬币朝上，朝上硬币位置分布在的翻硬币游戏中，SG值是等于k个独立的开始时只有一个硬币朝上的翻硬币游戏的SG值异或和。比如THHTTH这个游戏中，2号、3号、6号位是朝上的，它等价于TH、TTH、TTTTTH三个游戏和，即sg[THHTTH]=sg[TH]^sg[TTH]^sg[TTTTTH].我们的重点就可以放在单个硬币朝上时的SG值的求法。

推荐博客：http://www.cnblogs.com/kuangbin/p/3218060.html（翻硬币模型的8种变形）

总结：对于每种模型，先将其变成求单个位置上的sg值，如：T,FT,FFT,FFFT（F表示反面，T表示正面），再根据游戏规则求出该位置的后驱有几种情况，并且求出每种情况的SG值是多少，进而得到该位置的SG值。然后根据前几组数据找规律

注意：对于本题而言，对于某个位置i来说，当二进制表示下1的个数为1时sg[i]=2*i，否则为sg[i]=2*i+1。特别注意本题的输入数据可能包含同一个位置的硬币，所以需要用set记录已经使用过的位置

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<set>
 5 using namespace std;
 6 set<int>st;
 7 
 8 bool judge(int x)
 9 {
10     int cnt=0;
11     for ( int i=0;(1<<i)<=x;i++ ) {
12         int y=1<<i;
13         if ( y&x ) cnt++;
14     }
15     if ( cnt%2==1 ) return true;
16     else return false;
17 }
18 
19 int main()
20 {
21     int n,i,j,k,x,y,z,ans;
22     while ( scanf("%d",&n)!=EOF ) {
23         ans=0;
24         st.clear();
25         for ( i=0;i<n;i++ ) {
26             scanf("%d",&x);
27             if ( st.find(x)!=st.end() ) continue;
28             st.insert(x);
29             if ( judge(x) ) x=2*x;
30             else x=2*x+1;
31             ans^=x;
32         }
33         if ( ans ) printf("No
");
34         else printf("Yes
");
35     }
36     return 0;
37 }

HDOJ3537

反nim博弈：

1.（HDOJ2509）http://acm.hdu.edu.cn/showproblem.php?pid=2509

题意：有n堆，每堆有a[i]个，现在每次可以从第i堆中取[1,a[i]]个，谁取到最后一个谁输（nim博弈为谁取到最后一个谁赢）

分析：首先给出结论：先手胜当且仅当 ①所有堆石子数都为1且游戏的SG值为0（即有偶数个孤单堆-每堆只有1个石子数）；②存在某堆石子数大于1且游戏的SG值不为0.

给出简略证明：对于①来说当每堆石子数都为1时最后的结果一定是固定的，所以易得当有偶数堆1时最后先手一定会输，反之先手一定会赢

对于②来说。先假设只有一堆（记作第X堆）的石子数个数大于1（此时游戏的SG值一定不为0），对于剩下的堆数则满足①，若剩下石子数为1的堆数为奇数，为确保先手获胜，那么先手直接取完第X堆中的所有石子。若剩下石子数为1的堆数为偶数，那么我们可以将第X堆的石子取到只剩1个，那么对于该游戏来说石子数为1的堆数变成了奇数。

当石子数大于1的堆数超过一堆时，此时若游戏的SG值不为0时，先手只需要将游戏的SG值变成0，剩下的事就大体同Nim博弈了，只是Nim博弈最后取走最后一堆的所以石子，而此题最后一堆时只需要留一颗石子即可

 1 #include<cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n,ans,i,x;
 7     bool flag;
 8     while ( scanf("%d",&n)!=EOF ) {
 9         ans=0;
10         flag=false;
11         for ( i=1;i<=n;i++ ) {
12             scanf("%d",&x);
13             ans^=x;
14             if ( x>1 ) flag=true;
15         }
16         if ( flag ) {
17             if ( ans==0 ) printf("No
");
18             else printf("Yes
");    
19         }
20         else {
21             if ( n%2 ) printf("No
");
22             else printf("Yes
");
23         }
24     }
25     return 0;
26 }

HDOJ2509

2.（HDOJ1907）http://acm.hdu.edu.cn/showproblem.php?pid=1907

同上

 1 #include<cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n,ans,i,x,T;
 7     bool flag;
 8     scanf("%d",&T);
 9     while ( T-- ) {
10         scanf("%d",&n);
11         ans=0;
12         flag=false;
13         for ( i=1;i<=n;i++ ) {
14             scanf("%d",&x);
15             ans^=x;
16             if ( x>1 ) flag=true;
17         }
18         if ( flag ) {
19             if ( ans==0 ) printf("Brother
");
20             else printf("John
");    
21         }
22         else {
23             if ( n%2 ) printf("Brother
");
24             else printf("John
");
25         }
26     }
27     return 0;
28 }

HDOJ1907

SG值相关：

1.（HDOJ3980）http://acm.hdu.edu.cn/showproblem.php?pid=3980

题意：有一串长度为n的珠子组成的圆环，每次必须将连续的m个珠子涂色（等效为取出柱子），当没有连续的m个珠子可以涂色时则判负

分析：首先对n<m&&n==m这两种情况进行特判。对于n>m的情况第一次取出m颗柱子，将圆环变成直线，同时先手变后手，后手变先手。对于剩下的n-m个珠子来说，从小到大求出每个位置对应的sg值，具体求法是考虑其每个后继点（若将一串变成两串，则需要将两串对应长度的SG值进行异或操作）的SG值，进而得到该位置的SG值

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1005;
 6 int sg[maxn];
 7 bool vis[maxn];
 8 
 9 int main()
10 {
11     int T,i,j,k,h,x,y,z,n,m;
12     scanf("%d",&T);
13     for ( h=1;h<=T;h++ ) {
14         scanf("%d%d",&n,&m);
15         printf("Case #%d: ",h);
16         if ( n<m ) printf("abcdxyzk
");
17         else if ( n==m ) printf("aekdycoin
");
18         else {
19             n-=m;
20             memset(sg,0,sizeof(sg));
21             for ( i=m;i<=n;i++ ) {
22                 memset(vis,false,sizeof(vis));
23                 vis[sg[i-m]]=true;
24                 for ( j=1;j<(i-m)/2+1;j++ ) {
25                     x=j;
26                     y=i-m-j;
27                     z=sg[x]^sg[y];
28                     vis[z]=true;
29                 }
30                 for ( j=0;j<=i;j++ ) {
31                     if ( !vis[j] ) {
32                         sg[i]=j;
33                         break;
34                     } 
35                 }    
36             }    
37             if ( sg[n]==0 ) printf("aekdycoin
");
38             else printf("abcdxyzk
");
39         }
40     }    
41     return 0;
42 }

HDOJ3980

2.（HDOJ1944）http://acm.hdu.edu.cn/showproblem.php?pid=1944

题意：变形版的NIm，有n堆石子，每堆有num[i]个石子，但是每次取的石子数是有限制的，只有m种取法（f[1],f[2]……f[m]个），求先手是否会获胜

分析：计算对于一堆i个的石子其对应的SG值是多少，采用打表法

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 const int maxn=10010;
 7 const int maxm=110;
 8 const int N=10000;
 9 int sg[maxn],f[maxm],num[maxm];
10 bool vis[maxn];
11 vector<int>G[maxm];
12 
13 int main()
14 {
15     int n,m,i,j,k,x,y,z,q,maxx,ans;
16     while ( scanf("%d",&m)!=EOF && m ) {
17         for ( i=1;i<=m;i++ ) scanf("%d",&f[i]);
18         scanf("%d",&q);
19         maxx=N;
20         for ( i=1;i<=q;i++ ) G[i].clear();
21         for ( i=1;i<=q;i++ ) {
22             scanf("%d",&num[i]);
23             for ( j=0;j<num[i];j++ ) {
24                 scanf("%d",&x);
25                 maxx=max(maxx,x);
26                 G[i].push_back(x);
27             }
28         }
29         memset(sg,0,sizeof(sg));
30         for ( i=1;i<=maxx;i++ ) {
31             memset(vis,false,sizeof(vis));
32             for ( j=1;j<=m;j++ ) {
33                 if ( f[j]<=i ) vis[sg[i-f[j]]]=true;
34             }
35             for ( j=0;j<=i;j++ ) {
36                 if ( !vis[j] ) {
37                     sg[i]=j;
38                     break;
39                 }
40             }
41         }
42         for ( i=1;i<=q;i++ ) {
43             ans=0;
44             for ( j=0;j<num[i];j++ ) {
45                 x=G[i][j];
46                 ans^=sg[x];
47             }
48             if ( ans==0 ) printf("L");
49             else printf("W");
50         }
51         printf("
");
52     }
53     return 0;
54 }

HDOJ1944

3.（HDOJ1404）http://acm.hdu.edu.cn/showproblem.php?pid=1404（暴力打表求SG）

题意：给定一段最大长度为6的字符串，先有两种操作，第一种是将某个位置的值变成比他小的数，第二种是若某一位置为0则将该位置及其后面的字符都删去，谁删去最后一个字符谁赢

分析：因为最大长度为6，所以可以考虑采用暴力的方式算出[1,1e6]范围内的sg值。对于0来说一定是个必胜点，而1一定是个必败点。故有sg[0]=1,sg[1]=0。那么对于那些能转化到1的数字来说都是必胜点（此题的SG值只考虑0/1），因此可以考虑从头到尾进行遍历，当一个位置是必败点时，则从该位置进行转化，转化得到的点都是必胜点。转化有两种方式，其中之一是分别扩大每一位，第二种方式是往后添加位数（先添0，再添其他），如对于1来说，10xxxx都是可以通过转化得到的。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 const int maxn=1e6+10;
 7 const int N=1e6;
 8 bool sg[maxn];
 9 
10 int num(int m)
11 {
12     if ( m<10 ) return 1;
13     else if ( m<100 ) return 2;
14     else if  ( m<1000 ) return 3;
15     else if ( m<10000 ) return 4;
16     else if ( m<100000 ) return 5;
17     else return 6; 
18 }
19 
20 void dfs(int m)
21 {
22     int i,j,k,x,y,cnt,n,q;
23     cnt=num(m);
24     for ( i=1;i<=cnt;i++ ) {
25         x=pow(10,i-1);
26         q=m/x%10;
27         n=m;
28         for ( j=q;j<9;j++ ) {
29             n+=x;
30             sg[n]=true;
31         }
32     }
33     y=m;
34     k=1;
35     while ( cnt<6 ) {  
36         y*=10;
37         for ( i=0;i<k;i++ ) sg[y+i]=true;
38         k*=10;
39         cnt++; 
40     }  
41 }
42 
43 int main()
44 {
45     int i,j,k,n,x;
46     char s[10];
47     memset(sg,false,sizeof(sg));
48     sg[0]=true;
49     for ( i=1;i<N;i++ ) {
50         if ( !sg[i] ) dfs(i);
51     }
52     while ( scanf("%s",s)!=EOF ) {
53         n=0;
54         if ( s[0]=='0' ) {
55             printf("Yes
");
56             continue;
57         }
58         for ( i=0;s[i];i++ ) {
59             x=s[i]-'0';
60             n=n*10+x;
61         }
62         if ( sg[n] ) printf("Yes
");
63         else printf("No
");
64     }
65     return 0;
66 }

HDOJ1404

Every-SG博弈：

1.（HDOJ3595）http://acm.hdu.edu.cn/showproblem.php?pid=3595

Every-SG博弈：有N个游戏同时进行，每个游戏有两堆石子，每次从个数多的堆中取走数量小的数量的整数倍的石子。取最后一次的获胜。并且N个游戏同时进行，除非游戏结束，否则必须操作。

同时进行，必须操作这就是Every-SG的特点。

题意：两个人玩游戏，每次只能在石子数多的那一堆取出石子数少的那一堆的 $k$

$k$

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1010;
 6 const int inf=1e9;
 7 int step[maxn][maxn],sg[maxn][maxn];
 8 
 9 int getstep(int a,int b)
10 {
11     if ( sg[a][b]!=-1 ) return sg[a][b];
12     if ( a>b ) swap(a,b);
13     int M,mi;
14     M=-1,mi=inf;
15     for ( int i=a;i<=b;i+=a ) {
16         int k=getstep(a,b-i);
17         if ( k==0 ) {
18             M=max(M,step[a][b-i]);
19             sg[a][b]=sg[b][a]=1;
20         }
21         else mi=min(mi,step[a][b-i]);
22     }
23     if ( sg[a][b]==1 ) step[a][b]=step[b][a]=M+1;
24     else {
25         step[a][b]=step[b][a]=mi+1;
26         sg[a][b]=sg[b][a]=0;
27     }
28     return sg[a][b];
29 }
30 
31 int main()
32 {
33     int n,i,j,k,m,x,y,z,a,b,ans;
34     while ( scanf("%d",&n)!=EOF ) {
35         memset(sg,-1,sizeof(sg));
36         ans=-1;
37         for ( i=0;i<=1000;i++ ) {
38             sg[i][0]=sg[0][i]=0;
39             step[i][0]=step[0][i]=0;
40         }
41         for ( i=0;i<n;i++ ) {
42             scanf("%d%d",&a,&b);
43             getstep(a,b);
44             ans=max(ans,step[a][b]);
45         }
46         if ( ans%2 ) printf("MM
");
47         else printf("GG
"); 
48     }
49     return 0;
50 }

HDOJ3595