hdu4994——Revenge of Nim（博弈）

Problem Description

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.

—Wikipedia

Today, Nim takes revenge on you. The rule of the game has changed a little: the player must remove the objects from the current head(first) heap. Only the current head heap is empty can the player start to remove from the new head heap. As usual, the player who takes the last object wins.

Input

The first line contains a single integer T, indicating the number of test cases.

Each test case begins with an integer N, indicating the number of heaps. Then N integer Ai follows, indicating the number of each heap successively, and the player must take objects in this order, from the first to the last.

[Technical Specification]

1. 1 <= T <= 100

2. 1 <= N <= 1 000

3. 1 <= Ai <= 1 000 000 000

Output

For each test case, output “Yes” if the first player can always win, otherwise “No”.

Sample Input

2

1

2

2

1 1

Sample Output

Yes

No

找必勝點和必敗點，從後往前找，最後一個一定是必勝點，是以要求前一個一定要是另一個人拿到最後一堆，如果這一個隻有一個，那還要根據前面的來判斷，但如果是大于一個，那隻要第一個人有機會拿這堆，這能拿到隻剩下一個給另一個人，是以還要預先處理所有堆

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <math.h>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
#define MAXN 100005
#define Mod 1000000007
using namespace std;
long long num[];
int deal[];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=; i<n; ++i)
            scanf("%I64d",&num[i]);
        if(num[]==)
            deal[]=;
        if(num[]>)
            deal[]=;
        for(int i=;i<n;++i)
        {
            if(num[i-]==)
            {
                if(deal[i-]==)
                    deal[i]=;
                else if(deal[i-]==)
                    deal[i]=;
                else
                    deal[i]=;
            }
            else
                deal[i]=;
        }
        int pre=,flag=;
        for(int i=n-; i>; --i)
        {
            if(pre==)
                pre=;
            else
                pre=;
            if(num[i]>)
            {
                if(pre==&&deal[i]==)
                {
                    flag=;
                    break;
                }
                else if(pre==&&deal[i]==)
                    pre=;
                else if(pre==&&deal[i]==)
                    pre=;
                else if(pre==)
                    pre=;
            }
        }
        if(flag)
            printf("No\n");
        else
        {
            if(pre==)
                printf("Yes\n");
            else
            {
                if(num[]>)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
    }
    return ;
}