题解：P2197 【模板】Nim 游戏

· · 题解

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

思路

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

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

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

反之亦然。

我们从简单模型开始。

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)。


#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;
}