原題：

https://www.acwing.com/problem/content/3424/

題目大意：?

A、B兩人的數初始值均為0，他們輪流從X數組中取數，可以將該數與自己的數或對方的數進行異或操作，A先手，當X中的數被取完的時候誰的數大誰贏。兩人每次的操作都是最優的。判斷最后是A贏還是B贏還是平局。

一般博弈的問題測試數據范圍都比較大，所以肯定要找規律，找到必勝態和必敗態。

第一次做這種博弈問題，花了很長時間理解，所以記錄一下/(ㄒoㄒ)/~~。

1. 怎樣比較最終兩人的數字的大小？

比較a、b兩個二進制數的大小，可以從高位向低位逐位比較，當發現某一位數字不一樣時，就可以判斷a、b兩數的大小關系。

所以本題要對a、b最后的結果從高到低逐位比較。

由于a, b初始均為0，0與任何數異或結果還是這個數，所以最終a, b都是X中的一些數異或起來的結果，而對兩個二進制數的某個對應位進行異或操作時不會影響到其他位，所以可以不管a, b最后的值具體是多少，直接從高到低逐位比較X數組中每個數。

例如，假設X = [1, 2, 3, 4, 5]，就直接像下面這樣從高到低一位一位地比較，直到找到能分出勝負的那一位：

2. 怎樣分出勝負？

我們需要一位一位地看能不能分勝負。

異或運算時，0不能改變數，只有1才能改變。

以上面為例，這五個數中最高位有兩個1，兩個1能不能分勝負呢？

看上面的這張圖，初始時a，b的這一位都是0，當有一個人選了1，a或b的這一位就會發生改變(把1異或給自己或者對方)，從上圖的(0，0)出發，沿著邊走兩次，要么還是(0, 0)，要么變成(1, 1)，所以這一位不能分出勝負。

其實我們也可以進一步看出，當這一位1有偶數個時，都不能分出勝負(從(0, 0)開始沿著邊走偶數次還是走到這兩位相同的地方)

那當這一位的1有奇數個時：由于偶數個1的時候是平局，所以誰拿到最后一個1，誰就會贏(因為兩人都采用最佳策略，所以可以根據現在的狀態決定這個1給自己還是對方)。而誰能拿到最后那個1取決于0的個數：

情況1：0有偶數個，例如：0 0 1 1 1，那么先手必勝，因為只要先拿走一個1，接下來后手就進入了一個雙偶的局面，不管后手拿什么都拿和他一樣的就行，都能拿到最后一個1

情況2：0有奇數個，例如：0 0 0 1 1 1，那么后手必勝，不管先手拿什么，都拿和他相反的，接下來就和上面類似，先手進入了雙偶的局面，后手只要一直跟先手拿一致的就能贏

還要注意一個特殊情況就是1只有一個，這時候不管0有幾個顯然先手必勝。

總結一下：

若某一位上1一共有偶數個，則這一位分不出勝負，繼續看下一位；

若某一位上1一共有奇數個，

當1有一個時，先手必勝；

當1不止一個時，若0有偶數個，則先手必勝；若0有奇數個，則后手必勝。

3. 用一個數組bits統計X中的數每一位上1的總個數

分析了勝負情況后，很自然地就要統計出每一位上所有Xi的1的個數，例如上面X = [1，2，3，4，5]的例子中，bits[0] = 3, bits[1] = 2, bits[3] = 2（從低位到高位統計）。

先定義一個函數處理單個數，之后再一個一個地處理，這段代碼如下：

def get_bit(num):  # 處理單個數哪一位是1，并累加到bits里idx = 0  # 指示bits數組的索引while num:bit = num & 1  # num和1與一下，就能獲得最低位是多少bits[idx] += bit # 這一位的值累加到bits數組對應的位上，可以得到1的個數num >>= 1  # 右移一位，處理num的更高一位idx += 1   # 索引加1

題目中Xi最大是2的20次方，也就是最多用21位表示，所以bits初始化為[0] * 21。

最后是我的ac code:

def get_bit(num):idx = 0while num:bit = num & 1bits[idx] += bitnum >>= 1idx += 1t = int(input())
for _ in range(t):tmp = list(map(int, input().split()))len_x = tmp[0]x = tmp[1:]bits = [0] * 21for xi in x:   # 統計Xi中的數每一位總共有幾個1get_bit(xi)ans = 0for i in range(20, -1, -1):  # 從高到低比較，所以要倒序遍歷if bits[i] % 2 == 0:  # 有偶數個1continueelse:       # 有奇數個1if bits[i] == 1:  # 有1個1ans = 1elif (len_x - bits[i]) % 2 == 0: # 有偶數個0ans = 1elif (len_x - bits[i]) % 2 == 1: # 有奇數個0ans = -1breakprint(ans)

思路參考：http://【寒假每日一題07 | 【藍橋杯省賽】異或數列 StarryCoding.109】https://www.bilibili.com/video/BV1wr421s73c?vd_source=9c4a17fd87c2018d071c433adb917522