博弈入门----SG
SG解题模型：
1.把原游戏分解成多个独立的子游戏，则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。
即sg(G)=sg(G1)^sg(G2)^...^sg(Gn)。
2.分别考虑没一个子游戏，计算其SG值。
SG值的计算方法：（重点） 1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);
2.可选步数为任意步，SG(x) = x;
3.可选步数为一系列不连续的数，用模板计算。
分割博弈
题意：长度为n的环，每次操作取m个连续的块染色，aek先手，轮流操作，不能继续操作的人输。
分析：长度为n的环，我们先让aek先取一段m，长度变成了n-m的链(这样可以使得往后每一次决策后状态相同).
局面由一个n变为两个长度为 x 和 n-x-m 子游戏了。由 SG 定理，SG(n)=SG(x)^SG(n-x-m)。再由 SG 函数的定义式 SG[u]=mex(seg[v]).然后进行记忆化搜索。SG[n-m]=0的时候就是先手必败的局面。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,m,sg[maxn];
int mex( int n )
{
if( sg[n]!=-1 ) return sg[n];
if( n<m ) return sg[n]=0;
int vis[maxn];
memset(vis,0,sizeof(vis));
for( int i=0;i+m<=n;i++ )
{
if( sg[i]==-1 ) sg[i]=mex(i);
if( sg[n-i-m]==-1 ) sg[n-i-m]=mex(n-i-m);
vis[sg[i]^sg[n-i-m]]=1;
}
for( int i=0;i<maxn;i++ )
{
if( vis[i]==0 )
{
sg[n]=i;
break;
}
}
return sg[n];
}
int main()
{
int T,cas=0;
cin>>T;
while( T-- )
{
cin>>n>>m;
memset(sg,-1,sizeof(sg));
printf("Case #%d: ",++cas);
if( m>n ) puts("abcdxyzk");
else if( m==n ) puts("aekdycoin");
else
{
n-=m;
puts( mex(n) ? "abcdxyzk" : "aekdycoin" );
}
}
return 0;
}
POJ2311
题意：一个n * m的方格纸，每次可以横着或者竖着切一刀。切出1*1格子的人算赢，问先手是否存在必胜战略。
分析：每次切割一定是至少从长度2开始切割，(2,3),(3,2),(2,2)局面都是先手必败的局面。那么我们根据决策进行sg打表。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
int sg[205][205];
int get_sg( int n,int m )
{
if( sg[n][m]!=-1 ) return sg[n][m];
bool vis[1010]={false};
for( int i=2;i<=n/2;i++ )
{
vis[get_sg(i,m)^get_sg(n-i,m)]=true;
}
for( int j=2;j<=m/2;j++ )
{
vis[get_sg(n,j)^get_sg(n,m-j)]=true;
}
int i=0;
while( vis[i] ) i++;
return sg[n][m]=i;
}
int main()
{
int n,m;
memset(sg,-1,sizeof(sg));
sg[2][2]=sg[2][3]=sg[3][2]=0;
get_sg(200,200);
while( cin>>n>>m )
{
if( sg[n][m] ) puts("WIN");
else puts("LOSE");
}
}取走-分割游戏博弈
题意：Alice和Bob轮流取N堆石子，每堆S[i]个，Alice先，每一次可以从任意一堆中拿走任意个石子，也可以将一堆石子分为两个小堆。先拿完者获胜。
分析：SG定理: .找到所有子局面的sg值然后异或运算得到总局面的sg答案。
我们要预处理出所有子局面的sg值。
- 对于当前一堆石子数量为i,考虑可以拿任意堆，枚举1-i堆的sg值标记。
- 将一堆分成两堆非空石子，标记sg[j],sg[i-j].
- 然后根据SG定理中的mex()求得当前i状态的sg值。
但是由于打表复杂度为n^2,那么我们只能从打表中找到规律。
通过观察可以发现，每i%4==0的sg值为i-1,i%4==3的sg值为i+1,其他i的sg值为i.
那么我们就可以O(1)判断一个状态的sg值。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int sg[maxn];
void init()
{
sg[0]=0;
sg[1]=1;
for( int i=1;i<=1000;i++ )
{
bool vis[1010]={false};
for( int j=0;j<=i;j++ )
{
vis[sg[j]]=true;
if( j==0 || j==i ) continue;
vis[sg[j]^sg[i-j]]=true;
}
int j=0;
while( vis[j] ) j++;
sg[i]=j;
}
/*
for( int i=1;i<=1000;i++ )
{
printf("%d ",sg[i]);
if( i%4==0 ) puts("");
}
*/
}
int get_sg( int x )
{
if( x%4==0 ) return x-1;
if( x%4==3 ) return x+1;
return x;
}
int main()
{
init();
int T;
scanf("%d",&T);
while( T-- )
{
int n,ans=0;
scanf("%d",&n);
for( int i=0;i<n;i++ )
{
int x;scanf("%d",&x);
ans^=get_sg(x);
}
if( ans==0 ) printf("Bob\n");
else printf("Alice\n");
}
}
练习题
HDU1536
题意：给定n堆石子和一个取数的集合。每次移走的数量必须是集合里面的数字。最后取完的人赢。求必胜策略。
分析：SG打表模板
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=1e4+10;
int sg[maxn],a[maxn];
int n;
bool vis[maxn];
int init_sg( int *s,int t )
{
memset(sg,0,sizeof(sg));
for( int i=1;i<maxn;i++ )
{
memset(vis,0,sizeof(vis));
for( int j=0;j<t;j++ )
{
if( i-s[j]>=0 ) vis[sg[i-s[j]]]=true;
}
int j=0;
while( vis[j] ) j++;
sg[i]=j;
}
}
int main()
{
int n;
while( cin>>n && n )
{
for( int i=0;i<n;i++ ) cin>>a[i];
sort(a,a+n);
init_sg(a,n);
int q;
cin>>q;
while( q-- )
{
int m,ans=0;
cin>>m;
for( int i=0;i<m;i++ )
{
int x;cin>>x;
ans^=sg[x];
}
if( ans ) printf("W");
else printf("L");
}
puts("");
}
}HDU1847
题目大意：一堆石子，每次可以取2^k(0<k<32),最后取完的赢。问必胜策略。(n<=1000)
分析：和上题一样，有个取数集合。直接sg打表。(数据范围比较小
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=1e3+10;
int sg[maxn],a[maxn];
int n;
bool vis[maxn];
int init_sg( int *s,int t )
{
memset(sg,0,sizeof(sg));
for( int i=1;i<maxn;i++ )
{
memset(vis,0,sizeof(vis));
for( int j=0;j<t;j++ )
{
if( i-s[j]>=0 ) vis[sg[i-s[j]]]=true;
}
int j=0;
while( vis[j] ) j++;
sg[i]=j;
}
}
int main()
{
a[0]=1;
for( int i=1;i<12;i++ ) a[i]=a[i-1]*2;
init_sg(a,12);
int n;
while( cin>>n )
{
if( sg[n] ) puts("Kiki");
else puts("Cici");
}
}打表观察sg函数，发现n是3的倍数有先手必败。
#include <iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
int sum=0;
cin>>s;
for(auto i: s)
{
sum+=i-'0';
}
if(sum%3)
cout<<"Alan"<<endl;
else
cout<<"Frame"<<endl;
}
return 0;
}HDU1848
题目大意:三堆石子，每次取石子只能去斐波那契数列数列的数字，最后取完的赢。问必胜策略。（n<=1000）
分析：sg打表。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=4e3+10;
int sg[maxn],a[maxn];
int n;
bool vis[maxn];
int init_sg( int *s,int t )
{
memset(sg,0,sizeof(sg));
for( int i=1;i<maxn;i++ )
{
memset(vis,0,sizeof(vis));
for( int j=0;j<t;j++ )
{
if( i-s[j]>=0 ) vis[sg[i-s[j]]]=true;
}
int j=0;
while( vis[j] ) j++;
sg[i]=j;
}
}
int main()
{
a[0]=a[1]=1;
for( int i=1;i<20;i++ ) a[i]=a[i-1]+a[i-2];
init_sg(a,20);
int n,m,q;
while( cin>>n>>m>>q && ( n || m || q ) )
{
if( sg[n]^sg[m]^sg[q] ) puts("Fibo");
else puts("Nacci");
}
}
投递快手等公司10个岗位 >
