题面:https://www.luogu.org/problem/P2197
本题的解法是把nim游戏看做是有向图游戏用SG函数来解的.
Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,m,x,f[10100],a[10010],sg[100010];
bool vis[100010];
void getSG(int n)
{
memset(sg,0,sizeof(sg));
for (int i=1; i<=n; i++)
{
memset(vis,0,sizeof(vis));
for (int j=0; f[j]<=i; j++)
vis[sg[i-f[j]]]=1;
for (int j=0; j<=n; j++)
if (!vis[j])
{
sg[i]=j; break;
}
}
}
int main()
{
for (int i=1; i<=10001; i++) f[i]=i;
getSG(10000);
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
int ans=0;
for (int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
ans^=a[i];
}
if (ans) printf("Yes\n");
else printf("No\n");
}
return 0;
}