
Problem Description:
Alice 和 Bob 在玩一个游戏。给定 k 个数字 a1,a2,……,ak。一开始,有n堆硬币,每堆各有 Xi 枚硬币。Alice 和 Bob 轮流选出一堆硬币,从中取出一些硬币。每次所选硬币的枚数一定要在 a1,a2,……,ak 当中。Alice先取,取光硬币的一方获胜。当双方都采取最优策略时,谁会获胜?题目保证a1,a2……中一定有1.
1<=n<=1000000
1<=k<=100
1<=Xi,ai<=10000
Input:
n=3
k=3
a={1,3,4}
x={5 ,6,7}
Output:
Alice
这和4.1.1中介绍的硬币问题类似,但那道题中只有一堆硬币,而本题中有n堆。如果依然用动态规划算法的话,状态数将高达O(X1*X2*……*Xn)。
为了更高效地求解这个问题,要了解一下Grundy值这一重要概念。利用它,不光是这个游戏,其他许多游戏都可以转换成前面所介绍的Nim。
让我们再来考虑一下只有一堆硬币的情况。硬币枚数所对应的Grundy值的计算方法如下。
int grundy(int x){
S={};
for(i=,……,k){
if(a_i<=x)
//将Grundy(x-a_i)加到S中
}
return //最小的不属于S的非负整数
}
也就是说,当前状态的Grundy值就是除任意一步所能转移到的状态的Grundy值以外的最小非负整数。这样的Grundy值,和Nim中的一个石子堆类似,有如下性质。
Nim中有x颗石子的石子堆,能够转移成0,1,……,x-1颗石子的石子堆;
从Grundy值为x的状态出发,可以转移到Grundy值为0,1,……,x-1的状态;
只不过,与Nim不同的是转移后的Grundy值也有可能增加。不过,对手总能选取合适的策略再转移回相同Grundy值的状态,所以对胜负没有影响。(但是,对于状态可能有循环时,需要注意不分胜负·达成平局(游戏不会结束)的情况。因为在这个游戏中,石子数始终是减少的,所以不会发生平局)
另外,上面的程序是用单纯的递归函数实现的,改成动态规划或记忆化搜索之后,就能够保证求解的复杂度为O(xk)。
了解了一堆硬币的Grundy值的计算方法之后,就可以将它看作Nim中的一个石子堆。Nim中为什么用如下方法判断胜负。
所有石子堆的石子数Xi的XOR
X1 XOR X2 XOR …… XOR Xk
为零则必败,否则必胜
Grundy值等价于Nim中的石子数,所以对于Grundy值的情况,有
所有硬币堆的Grundy值的XOR
grundy(X1) XOR grundy(X2) XOR ……XOR grundy(Xk)
为零则必败,否则必胜
不光是这个游戏,在许多游戏中,都可以根据“当前状态的Grundy值等于除任意一步所能转移到的状态的Grundy值以外的最小非负整数”这一性质,来计算Grundy值,再根据XOR来判断胜负。
//输入
int N,K,X[MAX_N],A[MAX_K];
//利用动态规划计算Grundy值的数组
int grundy[MAX_N+];
void solve(){
//轮到自己时剩0枚则必败
grundy[]=;
//计算grundy值
int max_x= *max_element(X,X+N);
for(int j=;j<max_x;j++){
set<int> s;
for(int i=;i<K;i++)
if(A[i]<=j)
s.insert(grundy[j-A[i]]);
int g=;
while(s.count(g)!=) g++;
grund[j]=g;
}
//判断胜负
int x=;
for(int i=;i<N;i++)
x^=grundy[x[i]];
if(x) puts("Alice");
else puts("Bob");
}
SG函数:
首先引入mex函数,mex(x)=未在集合S中出现,且不超过x的最小非负整数。
举个例子:
S={1,2,3},mex(4)=0;
S={0,1,2,3},mex(4)=4;
S={0,1,3},mex(4)=2;
这个看起来和推理毫不相关……好啦,开始回忆下推理过程吧!
我们在推理博弈时,引入了“必胜局势”和“必败局势”,并且我们发现:“必胜局势”可以转化为“必胜局势”或“必败局势,而”必败局势“只能转化为”必胜局势“。这意味着,谁拿到了”必败局势“,只能把”必胜局势“留给对方,那就只能乖乖走进对方布下的圈套,不断陷入”必败局势“喽!
再引入SG定理和SG函数,SG(x)=mex(SG(所有通过x能达到的”局势“)),那么对于n堆石子的取石子游戏,若SG(1)^SG(2)^……^SG(n)==0,则先手必败,否则先手必胜。(^为异或,即在二进制中,异或双方相同位取0,不同位取1.)
那么在实际做题时,就可以直接预处理出所有SG值,求结果时直接异或即可。
以这题为例,若每次最少取1,最多取3,那么:
SG(0)=0;
SG(1)=1,因为1可以取到0,而SG(0)=0,所以把0去掉后,未出现过的最小非负整数为1;
SG(2)=2,同理,2可以取到1或0,排除掉SG(0)和SG(1),未出现过的最小非负整数为2;
SG(3)=3;
SG(4)=0,因为4可以取到1,2,3,但不能取到0(最多取3个嘛!),所以虽然排除1,2,3,未排除0,最小非负整数为0;
SG(5)=1;
……以此类推;
因为只有一堆石子,不用异或,直接判断SG(x)是否等于0即可判断x是否为”必胜局势“
模板:
//f[]:可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];
void getSG(int n)
{
int i,j;
memset(sg,,sizeof(sg));
for(i=;i<=n;i++)
{
memset(hash,,sizeof(hash));
for(j=;f[j]<=i;j++)
hash[sg[i-f[j]]]=;
for(j=;j<=n;j++) //求mes{}中未出现的最小的非负整数
{
if(hash[j]==)
{
sg[i]=j;
break;
}
}
}
}