uva 1482

对于组合游戏的题；

首先把问题建模成NIM等经典的组合游戏模型；

然后打表找出，或者推出SG函数值；

最后再利用SG定理判断是否必胜必败状态；

 1 #include<cstdio>
 2 #define ll long long
 3 using namespace std;
 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,ans=0;
18         scanf("%d",&n);
19         for(int i=0;i<n;i++)
20         {
21             scanf("%lld",&a);
22             ans^=sg(a);
23         }
24         puts(ans==0?"NO":"YES");
25     }
26     return 0;
27 }

View Code