题解 P3480 【[POI2009]KAM-Pebbles】

· · 题解

Nim游戏基本模型 安利个人blog，感觉写的挺详细的： http://blog.csdn.net/A_Comme_Amour/article/details/79347291

希望这篇题解能都帮到初学者。 Nim游戏

从一个问题进入。

描述

今天我们要认识一对新朋友，Alice与Bob。 Alice与Bob总是在进行各种各样的比试，今天他们在玩一个取石子的游戏。 在这个游戏中，Alice和Bob放置了N堆不同的石子，编号1..N，第i堆中有Ai个石子。 每一次行动，Alice和Bob可以选择从一堆石子中取出任意数量的石子。至少取1颗，至多取出这一堆剩下的所有石子。 Alice和Bob轮流行动，取走最后一个石子的人获得胜利。 假设每一轮游戏都是Alice先行动，请你判断在给定的情况下，如果双方都足够聪明，谁会获得胜利？

讨论

这是一个古老而又经典的博弈问题：Nim游戏。

Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：

对于第三条，我们有更进一步的定义Position，我们将Position分为两类：

  1. P-position：在当前的局面下，先手必败
  2. N-position：在当前的局面下，先手必胜

它们有如下性质：

  1. 合法操作集合为空的局面是P-position
  2. 可以移动到P-position的局面是N-position
  3. 所有移动都只能到N-position的局面是P-position

算法实现 取子游戏算法实现——

步骤1:将所有终结位置标记为必败点（P点）； 步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点） 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ； 步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。

在这个游戏中，我们已经知道A[] = {0,0,…,0}的局面是P局面，那么我们可以通过反向枚举来推导出所有的可能局面，总共的状态数量为A1∗A2∗...∗AN。并且每一次的状态转移很多。 虽然耗时巨大，但确实是一个可行方法。

当然，我们这里会讲这个题目就说明肯定没那么复杂。没错，对于这个游戏有一个非常神奇的结论：

对于一个局面，当且仅当A1 xor A2 xor ... xor AN =0时，该局面为P局面。

如何证明这个结论呢？

SG函数

同样从一个问题进入。

描述

给定一个有向无环图和一个起始顶点上的一枚棋子，Alice和Bob交替的将这枚棋子沿有向边进行移动，无法移动者判负。问是否有必胜策略。

讨论

事实上，这个游戏可以认为是所有ICG游戏的抽象模型。也就是说，任何一个ICG游戏都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义SG(Sprague-Garundy)函数。

Sprague-Grundy Theorem

SG函数的建立

首先定义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函数的性质。首先，所有的没有出边的顶点，其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的定义是完全对应的）。

后手必胜当且仅当sg的异或和为0

解题模型

举个栗子

例如：取石子问题，有1堆n个的石子，每次只能取{1，3,4}个石子，先取完石子者胜利，那么各个数的SG值为多少？ sg[0]=0，f[]={1,3,4}, x=1时，可以取走1-f{1}个石子，剩余{0}个，mex{sg[0]}={0}，故sg[1]=1; x=2时，可以取走2-f{1}个石子，剩余{1}个，mex{sg[1]}={1}，故sg[2]=0； x=3时，可以取走3-f{1,3}个石子，剩余{2,0}个，mex{sg[2],sg[0]}={0,0}，故sg[3]=1; x=4时，可以取走4-f{1,3,4}个石子，剩余{3,1,0}个，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2; x=5时，可以取走5-f{1,3,4}个石子，剩余{4,2,1}个，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3； 以此类推.....

 x         0  1  2  3  4  5  6  7  8....
 sg[x]     0  1  0  1  2  3  2  0  1....

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

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

关于SG(x) = x % (m+1);和SG(x) = x;

模板 两种方法我觉得都是搜索

方法一：打表 f[]可以取走的石子个数,注意f[]需要从小到大排序 sg[]SG函数值；vis[]标记数组，用于求mex{} 

int f[MAXN],sg[MAXN];
bool vis[MAXN];
void getSG(int n)
{
    sort(f+1,f+1+n);
    memset(sg,0,sizeof(sg));
    for (int i=1; i<=n; i++)
    {
        memset(vis,0,sizeof(vis));
        for (int j=1; f[j]<=i; j++)//f排序是为了让每一种取法都循环到
            vis[sg[i-f[j]]]=1;
        for (int j=0; j<=n; j++)
        {
            if (vis[j]==0)
            {
                sg[i]=j; break;
            }   
        }
    }
}

方法二：dfs s数组是定义特殊取法规则的数组，注意要按照从小到大排序；n表示集合大小 SG函数要初始化为-1，每个集合只需初始化一遍 

int s[MAXN],sg[MAXN],n;
bool vis[MAXN];
int SG_dfs(int x)
{
    if (sh[x]!=-1)
        return sg[x];
    memset(vis,0,sizeof(vis));
    for (int i=0; i<n; i++)
    {
        if (x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int i=0;
    while (1)
    {
        if (!vis[i])
            return sg[x]=i;
        i++;
    }
}

拓展

SG函数与Nim游戏的联系？ 　　如果对于一个游戏，它是ICG。那么我们可以发现，对于此游戏的一种局面，ICG上的多个sg函数的值，如果看做多个石堆的话，就相当于一个nim游戏！我们来一步步推导：

通过这个sg函数，我们就可以把所有ICG游戏转换成nim游戏！

经典题目

一、Nim游戏

第一个当然是Nim game；

Nim游戏的变形

二、阶梯博弈

这也是十分经典的一类题，并且有许多变形

这种问题只需要考虑奇数的位置进行Nim游戏，因为石子在偶数位置是可以模仿操作的。 为什么呢？因为任何人移动了偶数层的石子后，另外一个人总是可以把他们再移到下一奇数层，那么奇数层拿到偶数层的石子就相当于是丢掉了。 所以就变成了只有奇数层的Nim游戏。

变形1

可以看做独立的问题，使用sg函数求mex （为什么可以看做独立的问题？） 变形2

因为会对以后的台阶造成影响，问题不是独立的。