NIM博弈

发表于

给定n堆物品，第i堆物品有a[i]个

两名玩家轮流行动，每次可以任选一堆，取走任意多的物品，可把一堆取光，但不能不取

取走最后一件物品者胜利 两人都采取最优策略 问先手是否必胜

游戏过程中面临的状态称为局面

整局游戏第一个行动的称为先手，第二个称为后手

NIM博弈不存在平局，只有先手必胜和后手必胜

所有物品都被取光是一个必败局面

此时显然a1 xor a2 xor……an =0

对于任意一个局面，如果a1 xor a2 xor……an =x 不等于0 设x的二进制表示下最高位的1在第k位，那么至少存在一堆物品ai 它的第k位为1

显然 ai xor x<ai

我们从ai堆中取走若干物品 使其变为ai xor x 就得到了一个各堆物品异或和为0的局面

对于任意局面 如果a1 xor a2……xor an =0那样无论如何取物品，得到的局面下异或和不为0

假设 ai 被取成了bi 并且a1 xor…bi xor… xor an =0

由异或运算消去律 ai=bi

与不能不取石子相矛盾

故当且仅当a1 xor a2…xor an 不等于0时先手必胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
using namespace std;
int T,n,ans,tmp;
int main(){
    scanf("%d",&T);
    while(T--){
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&tmp);
            ans^=tmp;
        }
        if(!ans)printf("No\n");
        else printf("Yes\n");
    }
}