【HDU1536】S-Nim (博弈,SG函数)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日
#include<cstdio>    
#include<algorithm>    
using namespace std;    
#define N 100+10    
int knum,mnum,lnum;    
int ans[N],si[N],hi[N],sg[10010];    
int mex(int x)//求x的sg值(可作为模版应用)  
{    
    if(sg[x]!=-1) return sg[x];    
    bool vis[N];  
    memset(vis,false,sizeof(vis));    
    for(int i=0;i<knum;i++)    
    {    
        int temp=x-si[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()    
{    
    while(scanf("%d",&knum) && knum)    
    {    
        for(int i=0;i<knum;i++) scanf("%d",&si[i]);    
        sort(si,si+knum);    
        memset(sg,-1,sizeof(sg));    
        sg[0]=0;    
        memset(ans,0,sizeof(ans));    
        scanf("%d",&mnum);    
        for(int i=0;i<mnum;i++)    
        {    
            scanf("%d",&lnum);    
            for(int j=0;j<lnum;j++)    
            {    
                scanf("%d",&hi[i]); ans[i]^=mex(hi[i]);//尼姆博弈  
            }    
        }    
        for(int i=0;i<mnum;i++)    
        {    
            if(ans[i]==0) printf("L");    
            else printf("W");    
        }    
        printf("\n");    
    }    
    return 0;    
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日