uvalive5059(SG)

题目连接：https://vjudge.net/problem/UVALive-5059

开始学SG，，

输入a较大，无法递推出所有sg值，打表找规律。。

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=110;
 4 int sg[maxn];
 5 int vis[maxn];
 6 
 7 int main()
 8 {
 9     sg[1]=0;
10     for(int i=2;i<=30;i++)
11     {
12         memset(vis,0,sizeof(vis));
13         for(int j=1;j*2<=i;j++) vis[sg[i-j]]=1;
14         for(int j=0;;j++) if(!vis[j])
15         {
16             sg[i]=j;
17             break;
18         }
19         printf("%d ",sg[i]);
20     }
21     return 0;
22 }

观察结果可得：

sg[x]=(x%2==0)? x/2:sg[x/2];

 1 #include<cstdio>
 2 #include<cstring>
 3 #define ll long long
 4 
 5 ll sg(ll x)
 6 {
 7     return x%2==0?x/2:sg(x/2);
 8 }
 9 
10 int main()
11 {
12     int t;
13     scanf("%d",&t);
14     while(t--)
15     {
16         int n;
17         ll a,v=0;
18         scanf("%d",&n);
19         for(int i=0;i<n;i++)
20         {
21             scanf("%lld",&a);
22             v^=sg(a);
23         }
24         if(v) puts("YES");
25         else puts("NO");
26     }
27     return 0;
28 }