POJ 3537 Crosses and Crosses(sg博弈）-白红宇

POJ 3537 Crosses and Crosses(sg博弈）

阅读量：5086 次

发布时间：2019-06-13

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

题目：在1*n 的棋盘里面，A和B都在里面画叉，如果谁可以画了一个叉后，可以连成3个叉，那谁胜利；

分析：首先考虑如果我在玩游戏，我最希望对手可以画出-x-x or -xx- ，这种情况，也就是说玩家就一定不可画成这样给对手制造机会；那可以当成画了一个叉后就分成了（x-3） , （x-2-i) ,两个游戏，那我们可以根据SG的性质来解决这种分解游戏的游戏

#include
      
       #include
       
        //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍//n是集合s的大小 S[i]是定义的特殊取法规则的数组int s[110],sg[10010],n;int SG_dfs(int x){    int i;    if(x<0)    return 0;    if(sg[x]!=-1)        return sg[x];    bool vis[110];    memset(vis,0,sizeof(vis));    for(i=1;i<=x;i++)    {        vis[SG_dfs(i-3)^SG_dfs(x-2-i)]=1;    }    int e;    for(i=0;;i++)        if(!vis[i])        {            e=i;            break;        }    return sg[x]=e;}int main( ){    int n;    memset(sg,-1,sizeof(sg));    while(scanf("%d",&n)!=EOF)    {        if(SG_dfs(n))        puts("1");        else        puts("2");    }}

View Code

转载于:https://www.cnblogs.com/shuaihui520/p/9580374.html

你可能感兴趣的文章