【LA5059】Playing With Stones （SG函数）

题意：有n堆石子，分别有a[i]个。两个游戏者轮流操作，每次可以选一堆，拿走至少一个石子，但不能拿走超过一半的石子。

谁不能拿石子就算输，问先手胜负情况

n<=100，1<=a[i]<=2e18

思路：打表找SG函数的规律

当n为偶数时，SG(n)=n/2

当n为奇数时，SG(n)=SG(n/2)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 typedef long long ll;
 7 using namespace std;
 8 #define N   110
 9 #define oo  10000000
10 #define MOD 1000000007
11 
12 ll sg(ll x)
13 {
14     if(x&1) return sg(x/2);
15     return x/2;
16 }
17 
18 int main()
19 {
20     int cas;
21     scanf("%d",&cas);
22     while(cas--)
23     {
24         int n;
25         scanf("%d",&n);
26         ll ans=0;
27         for(int i=1;i<=n;i++)
28         {
29             ll x;
30             scanf("%lld",&x);
31             ans^=sg(x);
32         }
33         if(ans) printf("YES
");
34          else printf("NO
");
35     }
36     return 0;
37 }
38