题目链接:https://vjudge.net/problem/UVA-1482
题意:
有n堆石子, 每堆石子有ai(ai<=1e18)。两个人轮流取石子,要求每次只能从一堆石子中抽取不多于一半的石子,最后不能取的为输家。
题解:
典型的SG博弈,由于ai的范围很大,所以不能直接求SG值,那么就打表SG值找规律,如下:
发现,当x为偶数时, SG[x] = x/2; 当x为奇数时, SG[x] = SG[x/2],即如下:
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = +; int SG[MAXN], vis[MAXN];
void table()
{
SG[] = SG[] = ;
for(int i = ; i<=; i++)
{
memset(vis, , sizeof(vis));
for(int j = ; j<=i/; j++) vis[SG[i-j]] = ;
for(int j = ;;j++) if(!vis[j]) {
SG[i] = j;
break;
}
} for(int i = ; i<=; i++) printf("%-2d ",i); putchar('\n');
for(int i = ; i<=; i++) printf("%-2d ",SG[i]); putchar('\n');
putchar('\n');
for(int i = ; i<=; i+=) printf("%-2d ",i); putchar('\n');
for(int i = ; i<=; i+=) printf("%-2d ",SG[i]); putchar('\n');
putchar('\n');
for(int i = ; i<=; i+=) printf("%-2d ",i); putchar('\n');
for(int i = ; i<=; i+=) printf("%-2d ",SG[i]); putchar('\n');
/*
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
0 0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
0 0 1 0 2 1 3 0 4 2 5 1 6 3 7
*/
} LL getSG(LL x){
return x%==?x/:getSG(x/);
} int main()
{
// table();
int T, n;
scanf("%d", &T);
while(T--)
{
LL a, v = ;
scanf("%d", &n);
for(int i = ; i<=n; i++)
{
scanf("%lld", &a);
v ^= getSG(a);
} if(v) printf("YES\n");
else printf("NO\n");
}
}