预备知识：
必胜点和必败点的概念：P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。
N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。
它们有如下性质：
合法操作集合为空的局面是P-position可以移动到P-position的局面是N-position所有移动都只能到N-position的局面是P-position有一部分博弈论的题只需要用数学归纳法找出PN状态的一般规律就可以解决，
例：
hdu 1847 Good Luck in CET-4 Everybody! 当 n = 0 时，显然为必败点，因为此时你已经无法进行操作了 当 n = 1 时，因为你一次就可以拿完所有牌，此时为必胜点 当 n = 2 时，也是一次就可以拿完，此时为必胜点 当 n = 3 时，要么就是剩一张要么剩两张，无论怎么取对方都将面对必胜点，这一点为必败点。 以此类推，最后你就可以得到； n ： 0 1 2 3 4 5 6 ... position： P N N P N N P ... 发现PN是有规律的，问题便很好解决首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个给定的有向无环图，定义关于图的每个顶点的SG函数sg如下：sg(x)=mex{ sg(y) | y是x的后继 }。也就是说，一个点的SG函数为在它所有后继中都未出现的最小的值。
来看一下SG函数的性质。首先，所有的没有出边的顶点，其SG值为0，因为它的后继集合是空集。然后对于一个sg(x)=0的顶点x，它的所有后继y都满足 sg(y)≠ 0。对于一个sg(x)≠ 0的顶点，必定存在一个后继y满足sg(y)=0。
这个时候你就应该有所发现了！SG函数的性质和N,P局面的性质非常相似！ 以上表明，顶点x所代表的postion是P-position当且仅当sg(x)=0（跟P-positioin/N-position的定义是完全对应的）。
这么说有些难理解，可以从经典的nim游戏进入（为了好举例，改动一下）：
甲，乙两个人玩Nim取石子游戏。
有1堆n个的石子，每次只能取{ 1, 3, 4 }个石子，先取完石子者胜利，那么各个数的SG值为多少？
SG[0]=0，f[]={1,3,4},
x=1 时，可以取走1 - f{1}个石子，剩余{0}个，所以 SG[1] = mex{ SG[0] }= mex{0} = 1;
x=2 时，可以取走2 - f{1}个石子，剩余{1}个，所以 SG[2] = mex{ SG[1] }= mex{1} = 0;
x=3 时，可以取走3 - f{1,3}个石子，剩余{2,0}个，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;
x=4 时，可以取走4- f{1,3,4}个石子，剩余{3,1,0}个，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;
x=5 时，可以取走5 - f{1,3,4}个石子，剩余{4,2,1}个，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;
以此类推.....
x 0 1 2 3 4 5 6 7 8....
SG[x] 0 1 0 1 2 3 2 0 1....
这个时候再来理解“后手必胜当且仅当sg的异或和为0”这句话：如果一个数的大于0，证明这个数的后继状态一定有0，证明他进行完这一步或者说取完石子便取完了，那他一定胜利，反之，其sg函数值为0的话，他就必输了。
求SG函数值的模板：
1 //f[]：可以取走的石子个数 2 //sg[]:0~n的SG函数值 3 //hash[]:mex{} 4 int f[N],sg[N],hash[N]; 5 void getSG(int n) 6 { 7 int i,j; 8 memset(sg,0,sizeof(sg)); 9 for(i=1;i<=n;i++) 10 { 11 memset(hash,0,sizeof(hash)); 12 for(j=1;f[j]<=i;j++) 13 hash[sg[i-f[j]]]=1; 14 for(j=0;j<=n;j++) //求mes{}中未出现的最小的非负整数 15 { 16 if(hash[j]==0) 17 { 18 sg[i]=j; 19 break; 20 } 21 } 22 } 23 } View Code
Hdu1848 Fibonacci again and again 洛谷 nim游戏 洛谷 取火柴游戏 洛谷 [ZJOI2009]取石子游戏 POJ 2484 A Funny Game POJ 2425 A Chess Game POJ 2960 S-Nim
转载于:https://www.cnblogs.com/71-111/p/9346976.html
