怎么理解SG函数及性质

本篇内容主要讲解"怎么理解SG函数及性质"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"怎么理解SG函数及性质"吧!

{

Sprague-Grundy函数性质

所有的终结点SG值为0（因为它的后继集合是空集）
SG为0的顶点，它的所有后继点都满足SG不为0
对于一个SG不为0的顶点，必定存在一个后继满足SG为0

满足组合游戏性质
所有SG为0定点对应P点，SG大于0顶点对应N点

}

hdu1847 Good Luck in CET-4 Everybody!

题意：

总共n张牌，双方轮流抓牌，每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…），抓完牌，胜负结果也出来了：最后抓完牌的人为胜者。给出n，问先手赢还是后手赢？

PS：当然这题可以直接推出 n%3==0必败，否则必胜。 //巴什博奕

下面介绍另外一种做法

SG值：一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。//同mex()函数

简单点来讲就是当前状态离最近一个必败点的距离。

SG(x)=mex（S）
S是x的后继状态的SG函数值集合

mex(S)表示不在S内的最小非负整数

我们枚举下牌数为0-10的SG值：
num： 0 1 2 3 4 5 6 7 8 9 10
sg值：0 1 2 0 1 2 0 1 2 0 1

#include#include#includeusing namespace std;const int maxn = 1000 + 10;int arr[11], sg[maxn];void pre() { //把1000以内的所有的可能一次拿的牌都算出来！     arr[0] = 1;    for(int i=1; i<=10; ++i) arr[i] = arr[i-1]*2;}int mex(int x) { //这是求解该点的sg值的算法函数(采用记忆化搜索)     if(sg[x]!=-1) return sg[x];    bool vis[maxn];    memset(vis, false, sizeof vis );    for(int i=0; i<10; ++i) {        int temp = x - arr[i];        if(temp<0) break;        sg[temp] = mex(temp);        vis[sg[temp]] = true;    }    for(int i=0; ; ++i) {        if(!vis[i]) {            sg[x] = i;            break;        }    }    return sg[x];}int main() {    int n;    pre();    while(scanf("%d", &n)!=EOF) {        memset(sg, -1, sizeof sg );        if(mex(n)) printf("Kiki\n");        else printf("Cici\n");    }    return 0;}

到此，相信大家对"怎么理解SG函数及性质"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！