山东省第二届 ACM 省赛 Simple Game （Nim+Bash）

Problem Description

Here is a simple game. In this game, there are several piles of stones and two players. The two players play in turn. In each turn, one can choose at least one pile and at most three piles to take away arbitrary number of stones from the pile (Of course the number of stones, which is taken away, cannot be zero and cannot be larger than the number of stones in the chosen pile). If after a player ′ s turn, there is no stone left, the player is the loser.

Suppose that the two players are all very smart. Your job is to tell whether the player who plays first can win the game or not.

Input

The input has multiple test cases. The first line of the input contains one integer C, which is the number of test cases. Each test case begins with a line contains one integer N(1 <= N <=10000),which is the number of piles. Then comes N positive integers, which are not larger than 10000000. These N integers represent the number of stones in each pile.

Output

For each test case, output “Yes” in a single line, if the player who play first will win, otherwise output “No”.

Example Input

2
2
1
1
4
2
2
2
2


Example Output

Yes
No


思路

Nim+Bash

Nim 博弈说的是有三堆石子，两人轮流从某一堆中取任意多的石子，规定每次至少取一个，取走最后一枚石子的人获胜。

Bash 博弈说只有一堆石子，两人轮流取，最少取一个，最多取 m 个，取走最后一枚石子的人获胜。

1/1 2/2 3/4 4/8
7 1 1 1 0
11 1 1 0 1
13 1 0 1 1
14 0 1 1 1
15 1 1 1 1

AC 代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;

int bin[25];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(bin,0,sizeof(bin));
int n;
scanf("%d",&n);
while(n--)
{
int k;
scanf("%d",&k);
for(int i=0; k; i++)
{
bin[i]+=k%2;
k>>=1;
}
}
bool flag=true;
for(int i=0; i<25; i++)
if(bin[i]%4!=0)
{
flag=false;
break;
}
printf(!flag?"Yes\n":"No\n");
}
return 0;
}