810.黑板異或游戲（博弈論）
1.題目描述
??黑板上寫著一個非負(fù)整數(shù)數(shù)組 nums[i] 狡刘。Alice 和 Bob 輪流從黑板上擦掉一個數(shù)字襟诸，Alice 先手瓦堵。如果擦除一個數(shù)字后，剩余的所有數(shù)字按位異或運算得出的結(jié)果等于 0 的話歌亲，當(dāng)前玩家游戲失敗菇用。 (另外，如果只剩一個數(shù)字陷揪，按位異或運算得到它本身惋鸥；如果無數(shù)字剩余，按位異或運算結(jié)果為 0悍缠。）
??換種說法就是卦绣，輪到某個玩家時，如果當(dāng)前黑板上所有數(shù)字按位異或運算結(jié)果等于 0飞蚓，這個玩家獲勝滤港。
??假設(shè)兩個玩家每步都使用最優(yōu)解，當(dāng)且僅當(dāng) Alice 獲勝時返回 true趴拧。
?原題鏈接：https://leetcode-cn.com/problems/chalkboard-xor-game
2.簡析
??這是leetcode一道hard難度的博弈論題溅漾，剛好復(fù)習(xí)完Y總的博弈論，拿這道題做一個練習(xí)加強(qiáng)著榴。
??首先添履，雖然博弈論這個問題本身很難，但是一般在筆試面試算法題中都只涉及一些簡單的博弈論脑又，即先手必贏或者先手必輸暮胧。而先手必贏和必輸之間又存在一定的轉(zhuǎn)化關(guān)系，想做出博弈論類的題目问麸，則必須弄清楚先手必勝和先手必敗之間的狀態(tài)轉(zhuǎn)移關(guān)系往衷。
先手必贏：一定可以執(zhí)行某個操作后轉(zhuǎn)移到先手必輸狀態(tài)；
先手必輸：不管如何操作一定會轉(zhuǎn)移到先手必贏狀態(tài)口叙；
??來看回本題炼绘，首先嗅战，我們假定數(shù)組所有數(shù)字異或為妄田，那么其先手必贏狀態(tài)有兩種：
，則先手必贏驮捍；
，這種情況东且，nums中一定存在一個不等于
的數(shù)(如果不存在這個數(shù)启具，由數(shù)組長度于是偶數(shù)，那么
鲁冯，使得
拷沸，從而進(jìn)入先手必敗狀態(tài)（
）;
??而先手必敗狀態(tài)如下：
滿足
撞芍，在這種情況下，要么先手轉(zhuǎn)為上述的先手必贏狀態(tài)1跨扮，要么轉(zhuǎn)為先手必贏狀態(tài)2序无，因此這種情況下先手是必敗的。
3.狀態(tài)轉(zhuǎn)移圖
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;
}
};
