Revenge of Nim hdu 4994 (博弈)

http://acm.split.hdu.edu.cn/showproblem.php?pid=4994

题意：现在有两个人在取石子，共有n堆石子，每堆石子取完后才可以取下一堆石子，最后一个取石子的人胜利输出'Yes',否则输出'No'

分析：要想看最后一堆石子是谁取走的，我们则需要判断在前n-1堆石子中，主动权在谁的手上。试想，除了在迫不得已的情况下（a[i]==1）不得不这么取，两个人都可以通过取（1-a[i]）不等的石子来确保自己手里的主动权。倘若在遇到比1大的数字时，只需要判断在这个数字前面有几个1，继而来判断现在主动权在谁的手上。

若有（ans%2==0）个1，则肯定是第一个人取得胜利，反之第二个人。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <string>

#include <vector>

#include <algorithm>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn = ;

typedef long long LL;

int a[maxn];

int main()

{

    int T, n;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%d", &n);

        memset(a, , sizeof(a));

        for(int i=; i<=n; i++)

            scanf("%d", &a[i]);

        if(n==) printf("Yes\n");

        else

        {

            int ans = ;

            for(int i=; i<n; i++)

            {

                if(a[i]>) break;

                 ans ++;

            }

            if(ans %  == )

                printf("Yes\n");

            else

                printf("No\n");

        }

    }

    return ;

}

巴特西

Revenge of Nim hdu 4994 (博弈)

最新文章

热门文章