hdu1907||poj3480 sg博弈-白红宇

hdu1907||poj3480 sg博弈

阅读量：5077 次

发布时间：2019-06-12

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

这题就相当于取火柴游戏的第二种。

题意：最后取到的人为败，每次只能从一堆中取>=1的个数。

看了点论文，真不知道这些人是真没想的，无线崇拜。表示：论文还没看懂。

按照下面这个做的。

我们提出定理里的两个限制：1、SG函数为不为0。2、有没有某单一游戏的SG函数大于1。

通过这两个限制，我们可以组合出4种情况：

（1）SG==0，有某单一游戏的SG>1。

（2）SG!=0，有某单一游戏的SG>1。（必胜SJ）

（3）SG==0，无某单一游戏的SG>1。(必胜SJ)

（4）SG!=0，无某单一游戏的SG>1。

View Code

// I'm lanjiangzhou//C#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            //C++#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       #include 
                        
                         #include 
                         
                          #include 
                          
                           using namespace std;//*************************OUTPUT*************************#ifdef WIN32#define INT64 "%I64d"#define UINT64 "%I64u"#else#define INT64 "%lld"#define UINT64 "%llu"#endif//**************************CONSTANT***********************#define INF 0x3f3f3f3f// aply for the memory of the stack//#pragma comment (linker, "/STACK:1024000000,1024000000")//endconst int maxn = 1010;int a[maxn];int main(){ int t; scanf("%d",&t); while(t--){ memset(a,0,sizeof(a)); int n; int flag=0; scanf("%d",&n); int t=0; for(int i=0;i
                           
                            1){ flag++; } t=(t^a[i]); } if(t==0){ if(flag){ printf("Brother\n"); } else printf("John\n"); } else if(t!=0){ if(flag){ printf("John\n"); } else printf("Brother\n"); } } return 0;}