来自一位 AFOer 的题解，解法针对的是博弈论并非算法。

思路

首先这个游戏肯定有必胜方法，不然这道题也就失去了意义。

我们进行一个很简单的推论：如果我这一步走向必胜，那么对方只有两个结果：

下一步走向必败。
没有下一步，直接输掉。

反之亦然。

我们从简单模型开始。

$n=0$ 时

由于不存在石子，甲开局就输了。

$n=1$ 时

当石子数量

a_1=0

时，问题退化成

n=0

。否则甲一口气拿走全部。

$n=2$ 时

正难则反。

甲若胜利，最后状态必然为：

a=[0,0]

。往前一步，轮到甲时，局面为：

a=[0,x]

。

因为甲需要必胜，所以默认双方聪明绝顶。为了构成这样的局面，乙就是别无选择地走向这个结局。所以轮到乙时，局面为：

a=[1,1]

。

一步步向前推，只要到乙操作时，

a_1=a_2

，那么甲必胜。所以开局时，若

a_1{=}\mathllap{/\,}a_2

，则甲必胜。

接下来我们的所有情况都可以用以上这个方法进行推导，我们就不展开了。

结论

当

a_0

\oplus

a_1

\oplus

…

\oplus

a_n=0

，甲必败，否则甲必胜。

代码

十分简单，只需要实现以上功能。复杂度：

O(Tn)

。

CPP


#include<bits/stdc++.h>
using namespace std;
int ans,T,a,n;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%d",&n);
        while(n--)
        {
			scanf("%d",&a);
            ans^=a;
        }
        if(ans==0)
        {
            printf("No\n");
        }
        else
        {
            printf("Yes\n");
        }
    }
    return 0;
}

题解：P2197 【模板】Nim 游戏

文章操作

思路

$n=0$ 时

$n=1$ 时

$n=2$ 时

结论

代码

相关推荐

评论

题解：P2197 【模板】Nim 游戏

文章操作

思路

n=0n=0n=0 时

n=1n=1n=1 时

n=2n=2n=2 时

结论

代码

相关推荐

评论

$n=0$ 时

$n=1$ 时

$n=2$ 时