多校6 1003 HDU5795 A Simple Nim (sg函数)-白红宇

多校6 1003 HDU5795 A Simple Nim (sg函数)

阅读量：5147 次

发布时间：2019-06-13

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

思路：直接打表找sg函数的值，找规律，没有什么技巧

还想了很久的，把数当二进制看，再类讨二进制中1的个数是必胜或者必败状态。。。。

打表：

1 // #pragma comment(linker, "/STACK:102c000000,102c000000") 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 // #include 
                  
                   16 using namespace std;17 #define clc(a,b) memset(a,b,sizeof(a))18 #define inf 0x3f3f3f3f19 #define lson l,mid,rt<<120 // #define rson mid+1,r,rt<<1|121 const int N = 1e5+10;22 const int M = 1e6+10;23 const int MOD = 1e9+7;24 #define LL long long25 #define LB long double26 // #define mi() (l+r)>>127 double const pi = acos(-1);28 const double eps = 1e-8;29 void fre(){freopen("in.txt","r",stdin);}30 inline int read(){ int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') { if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;}31 32 int g[1010]; 33 bool vis[1010];34 int sg(int x){35 if(g[x] != -1) return g[x];36 if(x == 0) return 0;37 if(x == 1) return 1;38 if(x == 2) return 2;39 if(x == 3) return 3;40 clc(vis,0);41 vis[0]=1;42 for(int i = 1; i < x; i++){43 for(int j=1; i+j

代码：

1 // #pragma comment(linker, "/STACK:102c000000,102c000000") 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 // #include 
                  
                   16 using namespace std;17 #define clc(a,b) memset(a,b,sizeof(a))18 #define inf 0x3f3f3f3f19 #define lson l,mid,rt<<120 // #define rson mid+1,r,rt<<1|121 const int N = 1e6+10;22 const int M = 1e6+10;23 const int MOD = 1e9+7;24 #define LL long long25 #define LB long double26 // #define mi() (l+r)>>127 double const pi = acos(-1);28 const double eps = 1e-8;29 void fre(){freopen("in.txt","r",stdin);}30 inline int read(){ int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') { if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;}31 32 int sg(int x){33 if(x%8==0) return x-1;34 if(x%8==7) return x+1;35 return x;36 }37 int main(){38 int T,n;39 scanf("%d",&T);40 while(T--){41 int sum=0;42 scanf("%d",&n);43 for(int i=1;i<=n;i++){44 int x;45 scanf("%d",&x);46 sum^=sg(x);47 }48 printf("%s\n",sum?"First player wins.":"Second player wins.");49 }50 return 0;51 }