810.黑板異或游戲（博弈論）

1.題目描述

??黑板上寫著一個非負整數數組 nums[i] 。Alice 和 Bob 輪流從黑板上擦掉一個數字，Alice 先手。如果擦除一個數字后，剩余的所有數字按位異或運算得出的結果等于 0 的話，當前玩家游戲失敗。 (另外，如果只剩一個數字，按位異或運算得到它本身；如果無數字剩余，按位異或運算結果為 0。）
??換種說法就是，輪到某個玩家時，如果當前黑板上所有數字按位異或運算結果等于 0，這個玩家獲勝。
??假設兩個玩家每步都使用最優(yōu)解，當且僅當 Alice 獲勝時返回 true。
?原題鏈接：https://leetcode-cn.com/problems/chalkboard-xor-game

2.簡析

??這是leetcode一道hard難度的博弈論題，剛好復習完Y總的博弈論，拿這道題做一個練習加強。
??首先，雖然博弈論這個問題本身很難，但是一般在筆試面試算法題中都只涉及一些簡單的博弈論，即先手必贏或者先手必輸。而先手必贏和必輸之間又存在一定的轉化關系，想做出博弈論類的題目，則必須弄清楚先手必勝和先手必敗之間的狀態(tài)轉移關系。

先手必贏：一定可以執(zhí)行某個操作后轉移到先手必輸狀態(tài)；
先手必輸：不管如何操作一定會轉移到先手必贏狀態(tài)；

??來看回本題，首先，我們假定數組所有數字異或為，那么其先手必贏狀態(tài)有兩種：

1. ，則先手必贏；
2. ，這種情況，nums中一定存在一個不等于的數(如果不存在這個數，由數組長度于是偶數，那么必為0)，因此先手總可以去掉一個不等于的數，使得^，從而進入先手必敗狀態(tài)（）;

??而先手必敗狀態(tài)如下：

滿足，在這種情況下，要么先手轉為上述的先手必贏狀態(tài)1，要么轉為先手必贏狀態(tài)2，因此這種情況下先手是必敗的。

3.狀態(tài)轉移圖

狀態(tài)轉移示意圖

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