HDU 3032 Nim or not Nim?(sg函数博弈) - c++编程基础

TOP

HDU 3032 Nim or not Nim?(sg函数博弈)

2015-07-20 17:40:34 来源: 作者: 【大中小】浏览:2次

题目地址：HDU 3032

这题是很好用来练习sg函数打表的一题。

下面是sg函数值打表代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL long long int sg[110000];//sg函数值打表代码 int getsg(int x) { int ans, i; int mex[11000]; memset(mex,0,sizeof(mex)); for(i=x-1; i>=0; i--)//当选择拿出石子时的sg后继标记 { mex[sg[i]]=1; } for(i=1; i<=x/2; i++)//当选择分成两堆时的sg后继标记 { ans=0; ans^=sg[i]; ans^=sg[x-i]; mex[ans]=1; } for(i=0;; i++)//最小的非sg后继数 { if(!mex[i]) { sg[x]=i; return sg[x]; } } } int main() { int t, n, x, sum, i; sg[0]=0; for(i=0; i<100; i++) { getsg(i); printf("sg[%d]->%d\n",i,sg[i]); } return 0; }

由输出结果可以看出来

sg[4k]=4k-1

sg[4k+1]=4k+1;

sg[4k+2]=4k+2;

sg[4k+3]=4k+4;

所以可以直接根据这个规律来判断所有情况下的sg值了。然后从头到尾异或过去就可以解出来了。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL long long int main() { int t, n, x, sum, i; scanf("%d",&t); while(t--) { scanf("%d",&n); sum=0; for(i=0;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Powershell管理SharePoint站点	下一篇：hdu5014 Number Sequence（异或运..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: