POJ 3537 Crosses and Crosses(sg博弈）

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

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

#include<stdio.h>

#include<string.h>

//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍

//n是集合s的大小 S[i]是定义的特殊取法规则的数组

int s[],sg[],n;

int SG_dfs(int x)

{

    int i;

    if(x<)

    return ;

    if(sg[x]!=-)

        return sg[x];

    bool vis[];

    memset(vis,,sizeof(vis));

    for(i=;i<=x;i++)

    {

        vis[SG_dfs(i-)^SG_dfs(x--i)]=;

    }

    int e;

    for(i=;;i++)

        if(!vis[i])

        {

            e=i;

            break;

        }

    return sg[x]=e;

}

int main( )

{

    int n;

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

    while(scanf("%d",&n)!=EOF)

    {

        if(SG_dfs(n))

        puts("");

        else

        puts("");

    }

}

巴特西

POJ 3537 Crosses and Crosses(sg博弈）

最新文章

热门文章