硬币游戏2&&Cutting Game—

Grundy值

当前状态的Grundy值就是除任意一步所能转移到的状态的Grundy值以外的最小非负整数，

以硬币问题一为例，可写成：

int init_grundy()

{

    sg[] = ;

    for(int i = ;i <= x;i++)   //递推求前x个SG值

    {

        set<int>st;

        for(int j = ;j < k;j++)

            if(a[j] <= i) st.insert(sg[i - a[j]]);

        int g = ;

        while(st.count(g))  g++;

        sg[i] = g;

    }

}

Grundy值有什么用呢？

它的作用是巨大的，利用它，不光可以解决这个问题，其它许多问题都可以转换成前面介绍的Nim问题，即问题的解等于子问题的异或和。

Nim问题为什么等于异或和之前口胡过，这些问题为什么等于子问题的Grundy值的异或和呢？

根据Grundy的定义，先看下Grundy的性质（与Nim对比）：

Nim中有x颗石子的石子堆，能够转移成0, 1, 2, ..., x-1可石子的石子堆
从Grundy值为x的状态出发，也能转移到Grundy值为0, 1, 2, ,,,,, x-1的状态

也就不难理解为什么是异或和了：当必败态为Grundy异或和为0是，能保证必败态只能变成必胜态；必胜态可以转成必败态。

为了保证Grundy值为x的状态能转移为小于x的状态，Grundy的定义设为不在子问题Grundy值中的最小值（也就是说小于x的Grundy值都存在于子问题中）//好像有点循环论证，，，醒醒，这也能叫证明，，，个人理解吧

也不难发现，Nim问是Grundy问题的特例，其单堆的Grundy值为x。

例题

1、硬币游戏2

就是个堆Grundy值得异或和，异或和为0先手必败，否则先手必胜。

2、Cutting Game

题目：有一张 $w \times h$ 个格子的长方形纸，两个人轮流切割，水平或者垂直的切成两部分，最小切出单个格子（$1 \times 1$）的一方获胜。当双方都采取最佳策略时，谁会获胜？

分析：

这样会发生分割的游戏，也能够计算Grundy值。（为啥啊？？）

当一张 $w \times h$ 的纸张分割成两张时，假设所得的纸张的Grundy值分别为 $g_1$ 和 $g_2$，则这两张纸对应的状态的Geundy值为 $g_1 \ XOR \ g_2$。

另外，易知，一旦切割出长或宽为1时，下一步就一定能够切出 $1 \times 1$的纸张，所以知道此时必败。因此切割纸张时总要保证长和宽至少为2.

不然，grundy(2,2) 时 st{ grundy(1,2)^grundy(1,2), grundy(2,1)^grundy(2,1) }，则sg[2]=1先手必胜；而实际上先手必败。

（为什么硬币问题不要考虑转译成必败态，不懂，哪个大佬能教教我）

#include<cstdio>

#include<set>

#include<cstring>

using namespace std;

const int maxw = +;

const int maxh = +;

int sg[maxw][maxh];

int grundy(int w, int h)

{

    //printf("%d %d\n", w, h);

    int& ret = sg[w][h];

    if(ret != -)  return ret;

    if(w== || h==)  return ret=;

    set<int>st;

    for(int i = ;i < w-;i++)  st.insert(grundy(i, h) ^ grundy(w-i, h));

    for(int i = ;i < h-;i++)  st.insert(grundy(w, i) ^ grundy(w, h-i));

    ret = ;

    while(st.count(ret))  ret++;

    return ret;

}

int w, h;

int main()

{

    memset(sg, -, sizeof(sg));

    while(scanf("%d%d", &w, &h) == )

    {

        if(grundy(w, h)==)  printf("LOSE\n");

        else  printf("WIN\n");

    }

    return ;

}

巴特西

硬币游戏2&&Cutting Game——Grundy值

Grundy值

例题

最新文章

热门文章