本文共 2219 字，大约阅读时间需要 7 分钟。

Good Luck in CET-4 Everybody! 大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是如此。当然，作为在考场浸润了十几载的当代大学生，Kiki和Cici更懂得考前的放松，所谓“张弛有道”就是这个意思。这不，Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。“升级”？“双扣”？“红五”？还是“斗地主”？当然都不是！那多俗啊~作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的：1、  总共n张牌;2、  双方轮流抓牌；3、  每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）4、  抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生~），并且每次都是Kiki先抓牌，请问谁能赢呢当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态。Good luck in CET-4 everybody!

Input

Sprague-Grundy 函数 sg 作用于图 (?, ? ) , 其参数是一个非负整数 ?，

??(?) = ???{? ≥ 0 ∶ ? ≠ ??(?) ??? ? ∈ ? (?)}.

? 的后继者的 Sprague-Grundy 函数值构成一个集合，??(?) 是不属于该集

合的一个最小非负整数。

为方便描述，定义 mex(minimal excludant) 运算，这是施加于一个集合的运

算，表示最小的不属于这个集合的非负整数。例如 mex{0,1,2,4}=3,mex{2,3,5}=0。

上面的定义可以写成：??(?) = ???{??(?) ∶ ? ∈ ? (?).}

依然以取石子博弈为例来计算 ??(?)，每次取的石子数只能来自 ? = {1, 2, 3}。

终态顶点 0，sg(0)=mex{}=0; 顶点 1 只能移动到 0，所以

sg(1)=mex{sg(0)} = 1,

sg(2)=mex{sg(0),sg(1)}=2,

sg(3)=mex{sg(0),sg(1),sg(2)}=3,

sg(4) =mex{sg(1),sg(2),sg(3)}=0…

很明显 ??(?) = ?%4。

这是笔者从老师给的资料里粘贴的，我也是今天才学的SG函数，具体证明请麻烦读者自行查找相关资料(￣ε(#￣)

AC代码：#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define maxn 1000000007typedef long long ll;int n,a[12],sg[1005],vis[1005];int main(){    for(int i=0;i<12;i++) //保存各种取法        a[i]=pow(2,i);    int k;    for(int x=0;x<=1000;x++)  //x为牌数    {        memset(vis,0,(x+1)*sizeof(int)); //赋初值        for(int i=0;i<10;i++)   //2^10>1000,所以i只用取到9        {            if(a[i]>x) break;            vis[sg[x-a[i]]]=1;     //标记sg[i]中的元素        }        for(k=0;vis[k];k++);    //注意有个分号，也就是说结束时vis[k]==0        sg[x]=k;    }    while(scanf("%d",&n)==1)    {        if(sg[n]) printf("Kiki\n");        else printf("Cici\n");    }    return 0;}
       
      
     
    
   

注：若是联合组合博弈，可以利用Sprague-Grundy 定理

回头看 Nim 博弈，设每堆石子数为 ?? ，易知每个子博弈的 SG 函数为

???(??) = ??，所以整个博弈的 sg 函数为：??(?1, ?2, … , ??) = ?1 ⊕ ?2 ⊕ … ⊕ ??

等于0，失败。

笔者刚学的博弈，如果有问题希望大佬们能多加指点(。・∀・)ノ

转载地址：https://blog.csdn.net/qq_44632981/article/details/97621269 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！