【題目描述】
初始時，Alice和Bob分別有一個整數(shù)a和b，有一個給定的長度為n的數(shù)列。a和b的初始值均為0。Alice和Bob輪流操作，Alice先手，每步可以從兩個選項中選一種：
選項1：從數(shù)列中選一個X;給Alice的數(shù)異或上。
選項2：從數(shù)列中選一個X;給Bob的數(shù)異或上。
每個數(shù)Xi只能用一次，當(dāng)每個數(shù)都被用過一遍后，游戲結(jié)束。擁有數(shù)大的一方獲勝，雙方數(shù)字相同即平局。
雙方都足夠聰明，都采用最優(yōu)策略，問誰能獲勝？

【輸入格式】
每個評測用例包含多組詢問。詢問之間彼此獨立。
輸入的第一行包含一個整數(shù)T，表示詢問數(shù)。
接下來T行每行包含一組詢問。其中第i行的第一個整數(shù)n；表示數(shù)列長度，隨后n個整數(shù)X1, X2,… Xm表示數(shù)列中的每個數(shù)。

【輸出格式】
輸出T行，依次對應(yīng)每組詢問的答案。
每行包含一個整數(shù)1、0或-1分別表示Alice勝、平局或敗。

【樣例輸入】
4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

【樣例輸出】
1
0
1
1

【評測用例規(guī)模與約定】
對于所有評測用例，1 ≤ T ≤ 200000，1 ≤ ∑Ti=1 ni ≤ 200000，0 ≤ Xi < 220。

---

【解題思路】
借鑒：該博客

首先明確，為什么給定一個數(shù)列，游戲的結(jié)局是確定的呢？
A贏的意思是：A能采取某種策略，不管B作何應(yīng)對，A保證自己一定能贏；
B贏的意思是：B能采取某種策略，不管A作何應(yīng)對，B保證自己一定能贏；
對于異或：0^X ——保持X ； 1^X——翻轉(zhuǎn)X；
偶數(shù)次翻轉(zhuǎn)將回到原來的狀態(tài)，即與偶數(shù)個1異或?qū)⒈３植蛔儭?/p>

最后兩個結(jié)果數(shù)A^B = a^b^sum ，其中sum為給定數(shù)列所有數(shù)的異或和，sum = X1^X2^...Xni，所以如果是平局（即A = B），則A^B=0（即 sum = 0）。

現(xiàn)在考慮sum != 0時，因為是按位異或，并且最后比較A和B兩值的大小，所以要從二進(jìn)制的最高位開始比較，如果最高位相等，比較次高位，以此往下比較，直到可以判斷出結(jié)果。

用一個int型數(shù)組res[i]表示二進(jìn)制的第i位上1的個數(shù)，如果某一位的res[i]為奇數(shù)，即該位上有奇數(shù)個1與a和b異或，比如有5個1，因為0不會改變狀態(tài),其（a,b）的狀態(tài)轉(zhuǎn)移過程一定是:（0，0）->翻轉(zhuǎn)->平局->翻轉(zhuǎn)->平局->翻轉(zhuǎn)，也就是說在平局不管是（0，0）或（1，1）的基礎(chǔ)上，Alice 和 Bob誰擁有最后一次翻轉(zhuǎn)權(quán)（也就是最后一個1），誰就贏得游戲！

那怎么讓最后一個1輪到自己身上？就要用到0了，因為0不會改變數(shù)的大小，但相當(dāng)于讓自己“輪空一次”。還是考慮上面5個1的情況：如果在最后一次翻轉(zhuǎn)之前（不管在什么位置）插入偶數(shù)個0，則最后一次1的翻轉(zhuǎn)權(quán)來到了先手 Alice，則先手勝出；如果在最后一次翻轉(zhuǎn)之前（不管在什么位置）插入奇數(shù)個0，則最后一次1的翻轉(zhuǎn)權(quán)來到了后手 Bob，則后手勝出。

因為Alice和Bob都“足夠聰明”，面對奇數(shù)個1，Bob一定要去“ 搶0 ”，自己才有一線生機(jī)，而Alice也要以“ 搶0 ”來作應(yīng)對，讓最后一次翻轉(zhuǎn)權(quán)回到自己手里，因為0的個數(shù)有限，最后決定勝負(fù)的就是0個數(shù)的奇偶性。

因此，如果某一位的res[i]為偶數(shù)，則游戲結(jié)果的這一位一定相等，考慮下一位 ；如果第i位上1的個數(shù)為 1，則一定是先手贏（輸出：“1”）；如果第i位上1的個數(shù)為大于1的奇數(shù)，0的個數(shù)為偶數(shù)，則先手贏（輸出：“1”）；如果第i位上1的個數(shù)為大于1的奇數(shù)，0的個數(shù)為奇數(shù)，則后手贏（輸出：“-1”）。

---

Java代碼：

import java.util.ArrayList; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();//該ArrayList用來暫存每次詢問結(jié)果，待最后一次詢問結(jié)束再統(tǒng)一輸出ArrayList<Integer> res = new ArrayList<>();//n次詢問for (int i = 0; i < n; i++) {int[] weis = new int[24]; //該數(shù)組用于存儲二進(jìn)制形式下每一位1的數(shù)量int m = scanner.nextInt();//長度為m的數(shù)列轉(zhuǎn)為二進(jìn)制并處理for (int j = 0; j < m; j++) {long l = scanner.nextLong();String string = Long.toBinaryString(l); //轉(zhuǎn)為二進(jìn)制String reStr = new StringBuilder(string).reverse().toString(); //反轉(zhuǎn)，即高低位反轉(zhuǎn)，便于存儲與后面處理//判斷二進(jìn)制形式下每一位是否為1for (int k = 0; k < reStr.length(); k++) {if (reStr.charAt(k) == '1') weis[k]++;}}//對每次詢問后每一位中1的個數(shù)判斷從而得到結(jié)果，并將結(jié)果先暫時存儲在ArrayList-res中for (int j = weis.length - 1; j >= 0; j--) {if (weis[j] % 2 == 0 && j == 0) {res.add(0);break;}else if (weis[j] % 2 == 0){continue;}if (weis[j] == 1){res.add(1);break;}else if (weis[j] % 2 == 1 && (m - weis[j]) % 2 == 0){res.add(1);break;}else if (weis[j] % 2 == 1 && (m - weis[j]) % 2 == 1){res.add(-1);break;}}}//輸出結(jié)果for (int x : res){System.out.println(x);}} }

總結(jié)

以上是生活随笔為你收集整理的第十二届蓝桥杯Java省赛A组试题：异或数列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。