异或数列【博弈、位运算】-创新互联

目录

1、题目

题目描述

输入描述

输出描述

输入输出样例

评测用例规模与约定

运行限制

2、问题分析

（1）异或

（2）Alice 与 Bob 的博弈过程

3、代码：

参考文献

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 a 和 b，初始值均为 0。

有一个给定的长度为 n​​ 的公共数列 ,,,Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：

选项 1：从数列中选一个 ​​​ 给 Alice 的数异或上，或者说令 a​ 变为 ​​。（其中 ​​ 表示按位异或）

选项 2：从数列中选一个 ​​​ 给 Bob 的数异或上，或者说令 b​​ 变为​​​。

每个数 ​​ 都只能用一次，当所有 ​ 均被使用后（n​​ 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。 现在双方都足够聪明，都采用最优策略，请问谁能获胜？

每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 T，表示询问数。

接下来 T 行每行包含一组询问。其中第 i​ 行的第一个整数 ​​ 表示数列长度，随后 ​​ 个整数 ​​ 表示数列中的每个数。

输出 T 行，依次对应每组询问的答案。 每行包含一个整数 1​​、0​ 或−1 分别表示 Alice 胜、平局或败。

示例 1

输入

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

输出

1
0
1
1

对于所有评测用例，，,。​

• 大运行时间：1s
• 大运行内存: 256M

题目来源：异或数列

异或就数学上来讲，就是两个数字如果相同，那么最终值为0；如果两个数字不相同，那么最终值为1。这这么说可能对解决这个问题没有多大的作用，下面对异或进行总结：

  异或可以总结成：0^x = x（保持 x 不变）, 1^x = （翻转 x ），即偶数次翻转将回到原来的状态，即与偶数个1异或将保持不变

首先，我们假设 Alice 和 Bob 对 a 和 b 进行一系列异或操作之后得到的数据是 A 和 B 。如果我们对最终得到的这两个数进行异或运算，即 A^B = a^b^sum，其中sum为给定数列所有数的异或和，即。

• 如果 Alice 和 Bob 是平局，即,因为a = b = 0 , 所以sum = 0。
• 如果 Alice 和 Bob 不是平局，那么我们就比较最后的结果，即 A 和 B，从最高位开始比较，谁大谁win；如果相等，那么比较次高位，后面依次进行。现在我们用numk[ i ]表示第 i 位上面k 的个数，位置的序号是从低位到高位的。例如 00110这个数字，num1[ 1 ] = 0, num1[ 2 ] = 1,num1[ 3 ] = 1, num1[ 4 ] = 0,​​​​​​​ num1 5 ] = 0。
  • 如果 num1[ i ] 是偶数，所以 ALice 和 Bob 这一位的结果是相等的（分析过程看下面的例子）。
  • 如果 num1[ i ] 是奇数，关键是最后一个1花落谁家。
    • ​​​​​​​当 num0[ i ] 是奇数时，那么选择0相当于本轮轮空。对于后手来说，如果它比先手多抢夺1个0，那它肯定赢；输出-1
    • 当 num0[ i ] 是偶数时，只要Alice抢夺偶数个0，那么Alice肯定赢。

这里举例说明：

a : 0

b : 0

序列：1  1  1  0

Alice：1,1

Bob：1,0

（a,b）--->（0,0） --->（1,1） --->（1,0）

                            （0,0）        （1,0）

由此可见前面的偶数个1

如果在Alice身上用了偶数个1，那么Bob身上肯定也用了偶数个1，偶数个1翻转为原始值，即在这位数字上相等。

  如果在Alice身上用了奇数个，那么Bob身上肯定也用了奇数个，两者在该位上的1都翻转了，所以两者也是平局。

即关键是最后一个1在谁手中，谁就是赢家

import java.util.Scanner;
//int类型数值范围：2^31=10^9

public class _异或数列 {
	static int MAX_NUM = 200010;
	
	//计算每一位1的数值和所有数值的异或值
	static int  count(int a[],int num[]) {
		int sum=0;
		for(int i=1;i<=a[0];i++) {
			sum^=a[i];
			int number = a[i];
			
			for(int j=1;j<21;j++) {
				if((number &1) == 1)
						num[j]++;
				number >>=1;
			}
		}
		return sum;
	}

	static void ans(int sum,int num[],int n) {
		//如果序列的异或结果为0，那么意味着这两个值与这些序列异或之后是相等的
		if(sum==0) {
			System.out.println(0);
			return;
		} 
		//对每一位的1进行操作，从低位开始计算，低位为1，高位为20
		for(int i=20;i>0;i--) {
			//第i位数字中所有0的个数
			int num0 = n-num[i];
			//最高位只有一个1，谁抢到了谁win
			if(num[i] == 1) {
				System.out.println(1);
				return;
			}
			
			if(num[i]%2==0)
				continue;
			if(num[i]%2==1) {
				if(num0%2==0) {
					System.out.println(1);
					return;
				}else {
					System.out.println(0);
					return;
				}
			}
		}
	}


	
	public static void main(String[] args) {
		System.out.println("Please input data:");
		//输入数据
		Scanner input = new Scanner(System.in);
		//定义存储公共序列数组，其中下标为0存储序列个数，1-n存储序列的值
		int [] a = new int[MAX_NUM];
		
		//输出询问数
		int all = input.nextInt(),sum;
		
		for(int i=0;i