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

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

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

打表：

 // #pragma comment(linker, "/STACK:102c000000,102c000000")

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <sstream>

 #include <string>

 #include <algorithm>

 #include <list>

 #include <map>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <cstdlib>

 // #include <conio.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define inf 0x3f3f3f3f

 #define lson l,mid,rt<<1

 // #define rson mid+1,r,rt<<1|1

 const int N = 1e5+;

 const int M = 1e6+;

 const int MOD = 1e9+;

 #define LL long long

 #define LB long double

 // #define mi() (l+r)>>1

 double const pi = acos(-);

 const double eps = 1e-;

 void fre(){freopen("in.txt","r",stdin);}

 inline int read(){int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;}

 int g[];

 bool vis[];

 int sg(int x){

     if(g[x] != -) return g[x];

     if(x == ) return ;

     if(x == ) return ;

     if(x == ) return ;

     if(x == ) return ;

     clc(vis,);

     vis[]=;

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

         for(int j=; i+j<x; j++){

             int t = ;

             int a = sg(i), b = sg(j),c=sg(x-i-j);

             t ^= a;

             t ^= b;

             t^=c;

             vis[a] = vis[b] =vis[c]=;

             vis[t] = ;

         }

         vis[g[i]]=;

     }

     for(int i = ;; i++) if(!vis[i])

             return i;

 }

 int main(){

     int n;

     clc(g,-);

     for(int i = ; i <= ; i++){

         g[i] = sg(i);

         printf("%d %d\n", i, g[i]);

     }

     return ;

 }

代码：

 // #pragma comment(linker, "/STACK:102c000000,102c000000")

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <sstream>

 #include <string>

 #include <algorithm>

 #include <list>

 #include <map>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <cstdlib>

 // #include <conio.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define inf 0x3f3f3f3f

 #define lson l,mid,rt<<1

 // #define rson mid+1,r,rt<<1|1

 const int N = 1e6+;

 const int M = 1e6+;

 const int MOD = 1e9+;

 #define LL long long

 #define LB long double

 // #define mi() (l+r)>>1

 double const pi = acos(-);

 const double eps = 1e-;

 void fre(){freopen("in.txt","r",stdin);}

 inline int read(){int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;}

 int sg(int x){

     if(x%==) return x-;

     if(x%==) return x+;

     return x;

 }

 int main(){

     int T,n;

     scanf("%d",&T);

     while(T--){

         int sum=;

         scanf("%d",&n);

         for(int i=;i<=n;i++){

             int x;

             scanf("%d",&x);

             sum^=sg(x);

         }

         printf("%s\n",sum?"First player wins.":"Second player wins.");

     }

     return ;

 }