uva1482：Playing With Stones （SG函数）

题意：有N堆石子，每次可以取一堆的不超过半数的石子，没有可取的为输。

思路：假设只有一堆，手推出来，数量x可以表示为2^p-1形式的必输。 但是没什么用，因为最后要的不是0和1，而是SG函数；所以必输的为0，那么其他的呢？

我们可以发现SG=0的位置是1，3，7，15，31....

                     SG=1，            2，5，11，23....

可以推出来，也可以打表。

（水题，这题可以放这里以后讲课用。

    sg[1]=0;
    for(int i=2;i<=30;i++){
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=i/2;j++) vis[sg[i-j]]=1;
        for(int j=0;;j++){
            if(!vis[j]) {sg[i]=j; break;}
        }
    }
    for(int i=1;i<=30;i++) cout<<i<<" "<<sg[i]<<endl;

完整代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll SG(ll x){
    if(x&1LL) return SG(x/2);
    return x/2;
}
int main()
{
    int T,N,ans; ll x,q;
    scanf("%d",&T);
    while(T--){
        ans=0; scanf("%d",&N);
        for(int i=1;i<=N;i++){
            scanf("%lld",&x);
            ans^=SG(x);
        }
        if(ans) puts("YES");
        else puts("NO");
    }
    return 0;
}