UVALive 5059 Playing With Stones(求sg函数)

题意和nim游戏差不多，就是取石子的时候最多只能拿原来的一半，比如一堆5个石子最多拿两个。

先用打表的方式看出前面一部分的sg值，然后找规律来做。

打表求sg值的程序才是最重要的。

#include<cstdio>
#include<cstring>
#define ll long long
int main() {
    int vis[50];
    int sg[50];
    sg[1] = 0;
    for(int i = 2; i <= 30; i++) {
        memset(vis, 0, sizeof(vis));
        for(int j = 1; j * 2 <= i; j++) vis[sg[i-j]] = 1;
        for(int j = 0; ; j++) if(!vis[j]) {
            sg[i] = j;
            break;
        }
        printf("%d ", sg[i]);
    }
}

#include<cstdio>
#include<cstring>
const int maxn = 110;
#define ll long long
ll sg(ll x) {
    return x % 2 == 0 ? x / 2 : sg(x / 2);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        ll ans = 0;
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            ll tmp;
            scanf("%lld", &tmp);
            ans ^= sg(tmp);
        }
        if(!ans) puts("NO");
        else puts("YES");
    }
}