P2599取石子游戏

P2599 [ZJOI2009]取石子游戏

题目描述

在研究过\(Nim\)游戏及各种变种之后，\(Orez\)又发现了一种全新的取石子游戏，这个游戏是这样的： 有\(n\)堆石子，将这\(n\)堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。 \(Orez\)问：对于任意给出一个初始一个局面，是否存在先手必胜策略。

输入格式

文件的第一行为一个整数\(T\)，表示有 \(T\)组测试数据。

对于每组测试数据，第一行为一个整数\(n\)，表示有\(n\)堆石子; 第二行为\(n\)个整数\(a_i\)，依次表示每堆石子的数目。

输出格式

对于每组测试数据仅输出一个整数\(0\)或\(1\)。其中\(1\)表示有先手必胜策略，\(0\)表示没有。

Solution

如果最靠外边的两堆不一样, 那就先取高的那一堆的一个

然后后手取了几个, 先手就会跟着后手在另一堆中取相同的个石子

易证当两堆的差大于\(1\)时, 后手一定会先取完一堆

先手该取的那一堆还有石子

谔谔, 出了一点小问题?

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e3 + 5;
int T, N, A[Maxn];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf ("%d", &N);
        for (int i = 0; i < N; ++i) scanf ("%d", A + i);
        if (abs(A[0] - A[N - 1]) <= 1) 
        {
            if (A[0] == 1 || A[N - 1] == 1) puts("1");
            else puts("0");
        }
        else puts("1");
    }
}