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

创新互联建站是一家专业提供沿滩企业网站建设,专注与网站制作、成都网站建设、H5场景定制、小程序制作等业务。10年已为沿滩众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。

1、题目

题目描述

输入描述

输出描述

输入输出样例

评测用例规模与约定

运行限制

2、问题分析

（1）异或

（2）Alice 与 Bob 的博弈过程

3、代码：

参考文献

1、题目题目描述

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

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

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

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

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

输入描述

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

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

接下来 T 行每行包含一组询问。其中第 i 行的第一个整数 n_i 表示数列长度，随后 n_i 个整数 $X_1, X_2, \cdots , X_{n_i}$ 表示数列中的每个数。

输出描述

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

输入输出样例

示例 1

输入

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

输出

评测用例规模与约定

对于所有评测用例， $1\leqslant T\leqslant 200000$ ， $1 \leq \sum\limits_{i=1}^T n_i \leq 200000$ , $0\leq X_i< 2^{20}$ 。

运行限制

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

题目来源：异或数列

2、问题分析（1）异或

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

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

（2）Alice 与 Bob 的博弈过程

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

如果 Alice 和 Bob 是平局，即 $A \oplus B = 0 = a \oplus b \oplus sum$ ,因为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在谁手中，谁就是赢家

3、代码：

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

参考文献蓝桥杯2021年第十二届省赛真题-异或数列
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
                

                网页题目：异或数列【博弈、位运算】-创新互联                

                文章源于：http://pwwzsj.com/article/doehje.html


        
            其他资讯
            
                
                        printf函数执行情况的示例分析-创新互联
                    

                        微信小程序如何实现页面之间的传参-创新互联
                    

                        Javascript中如何添加节点-创新互联
                    

                        好程序员web前端分享SDK与API之间的关系和联系-创新互联
                    

                        java中有哪些类是不能继承的？-创新互联