LeetCode-810.黑板异或游戏

810.黑板异或游戏（博弈论）

1.题目描述

黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）
换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。
假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。
原题链接：https://leetcode-cn.com/problems/chalkboard-xor-game

2.简析

这是leetcode一道hard难度的博弈论题，刚好复习完Y总的博弈论，拿这道题做一个练习加强。
首先，虽然博弈论这个问题本身很难，但是一般在笔试面试算法题中都只涉及一些简单的博弈论，即先手必赢或者先手必输。而先手必赢和必输之间又存在一定的转化关系，想做出博弈论类的题目，则必须弄清楚先手必胜和先手必败之间的状态转移关系。

先手必赢：一定可以执行某个操作后转移到先手必输状态；
先手必输：不管如何操作一定会转移到先手必赢状态；

来看回本题，首先，我们假定数组所有数字异或为 $prexor$ ，那么其先手必赢状态有两种：

$prexor = 0$ ，则先手必赢；

$prexor != 0，nums.size()\%2==0$ ，这种情况，nums中一定存在一个不等于 $prexor$ 的数(如果不存在这个数，由数组长度于是偶数，那么 $prexor$ 必为0)，因此先手总可以去掉一个不等于 $prexor$ 的数 $N_x$ ，使得 $prexor$ ^ $N_x != 0$ ，从而进入先手必败状态（ $prexor != 0，nums.size()\%2==1$ ）;

而先手必败状态如下：

满足 $prexor!=0，nums.size()\%2==1$ ，在这种情况下，要么先手转为上述的先手必赢状态1，要么转为先手必赢状态2，因此这种情况下先手是必败的。

3.状态转移图

状态转移示意图

4.代码示例

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        int prexor = 0;
        for(int num:nums) prexor ^= num;
        return prexor==0 || nums.size()%2==0;
    }
};