异或数列蓝桥杯_蓝桥杯 异或数列

本题是运用博弈的思想来解题

首先两个人如果分数相同那么他们异或的结果就是0，所以如果是平局也就是输入的所有数据的异或值为0，就是平局的情况了

那么解决完平局的情况，我们就要来解决如果不是平局，也就是这些数的某一二进制位置的1数字是不均等的，这样就会有赢家

那么我们就可以写代码了

首先我们把这些数据二进制的每个位置的1的个数记录下来，如果某个位置为奇数，那么就可以决出胜负了，我们从最高位向下

有三种情况

1 为奇数且这个位置1的数量为1，那么一定是先手胜利，因为他可以决定是让自己这一位变成1，还是让对方那位置变成0，所有先手必胜

2 为奇数，且总的数量为偶数，那么后手必胜

下面模拟

如果本位有3个1 1个0

那么如果A选择1，让自己变成1，B拿0对A或者对自己，剩下两个1，B必胜

如果A选择0，B选择1对自己，A防守，B再拿1对自己，或者A对自己，B方式，B必胜

3 为奇数，且总的数量为奇数，那么先手必胜 解释其实就是上面的翻版，先手可以选0，把自己变成后手，现在的情况就是2这种情况了

思路就是这样，一个博弈的题目，但是我确实不咋会博弈

参考：蓝桥杯2021年第十二届省赛-异或数列_9898zy998的博客-CSDN博客_蓝桥杯异或数列

下面上代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
 
public class Main异或数列 {
	public static int num[]=new int[21];
	public static void main(String[] args) throws IOException {
		StreamTokenizer x = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		x.nextToken();
		int n=(int)x.nval;
		while(n--!=0) {
			Arrays.fill(num, 0);
			x.nextToken();
			int m=(int)x.nval;
			long a=0;
			for(int i=0;i<m;i++) {
				x.nextToken();
				wys((long)x.nval);
				a^=(long)x.nval;
			}
			if(a==0) {//如果结果相同异或为0，也就是平局
				out.println(0);
				out.flush();
				continue;
			}
			for(int i=20;i>0;i--) {//从高位开始，数据是2^20,所以从开始
				if(num[i]==1) {//最高位为只有1个时，先手可以选择自己变1，和对手变0，所以先手必胜
					out.println(1);
					out.flush();
					break;
				}
				if(num[i]%2==1){//如果有奇数个，就看有多少个数字
					//如果有奇数个
					if(m%2==1) 
						out.println(1);
					else//偶数个
						out.println(-1);
					out.flush();
					break;
				}
			}
		}
	}
	public static void wys(long a){
	    int cnt=1;
	    while(a!=0){
	        if((a&1)!=0)num[cnt]++;//如果这位为1
	        cnt++;
	        a>>=1;
	    }
	}
}

 如有侵权，联系删