異或數(shù)列【博弈、位運算】-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)建站是一家專業(yè)提供沿灘企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站制作、成都網(wǎng)站建設(shè)、H5場景定制、小程序制作等業(yè)務(wù)。10年已為沿灘眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進行中。

1、題目

題目描述

輸入描述

輸出描述

輸入輸出樣例

評測用例規(guī)模與約定

運行限制

2、問題分析

（1）異或

（2）Alice 與 Bob 的博弈過程

3、代碼：

參考文獻

1、題目題目描述

Alice 和 Bob 正在玩一個異或數(shù)列的游戲。初始時，Alice 和 Bob 分別有一個整數(shù)?a?和?b，初始值均為?0。

有一個給定的長度為?n?? 的公共數(shù)列? X_1 , X_2 , $\cdots , X_n$ ,Alice 和 Bob 輪流操作，Alice 先手，每步可以在以下兩種選項中選一種：

選項 1：從數(shù)列中選一個? X_i ??? 給 Alice 的數(shù)異或上，或者說令?a??變?yōu)? $a \oplus X_i$ ??。（其中? $\oplus$ ?? 表示按位異或）

選項 2：從數(shù)列中選一個? X_i ??? 給 Bob 的數(shù)異或上，或者說令?b?? 變?yōu)?img alt="b \oplus X_i" src="/upload/otherpic6/gif.jpg" />???。

每個數(shù)? X_i ?? 都只能用一次，當(dāng)所有? X_i ??均被使用后（n?? 輪后）游戲結(jié)束。游戲結(jié)束時，擁有的數(shù)比較大的一方獲勝，如果雙方數(shù)值相同，即為平手。現(xiàn)在雙方都足夠聰明，都采用最優(yōu)策略，請問誰能獲勝？

輸入描述

每個評測用例包含多組詢問。詢問之間彼此獨立。

輸入的第一行包含一個整數(shù) T，表示詢問數(shù)。

接下來?T?行每行包含一組詢問。其中第?i? 行的第一個整數(shù)? n_i ?? 表示數(shù)列長度，隨后? n_i ?? 個整數(shù)? $X_1, X_2, \cdots , X_{n_i}$ ???表示數(shù)列中的每個數(shù)。

輸出描述

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

輸入輸出樣例

示例 1

輸入

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

輸出

評測用例規(guī)模與約定

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

運行限制

大運行時間：1s
大運行內(nèi)存: 256M

題目來源：異或數(shù)列

2、問題分析（1）異或

異或就數(shù)學(xué)上來講，就是兩個數(shù)字如果相同，那么最終值為0；如果兩個數(shù)字不相同，那么最終值為1。這這么說可能對解決這個問題沒有多大的作用，下面對異或進行總結(jié)：

? 異或可以總結(jié)成：0^x = x（保持 x 不變）, 1^x =? $\hat{x}$ （翻轉(zhuǎn) x ），即偶數(shù)次翻轉(zhuǎn)將回到原來的狀態(tài)，即與偶數(shù)個1異或?qū)⒈３植蛔?/p>（2）Alice 與 Bob 的博弈過程

首先，我們假設(shè) Alice 和 Bob 對 a 和 b 進行一系列異或操作之后得到的數(shù)據(jù)是 A 和 B 。如果我們對最終得到的這兩個數(shù)進行異或運算，即 A^B = a^b^sum，其中sum為給定數(shù)列所有數(shù)的異或和，即 $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 不是平局，那么我們就比較最后的結(jié)果，即 A 和 B，從最高位開始比較，誰大誰win；如果相等，那么比較次高位，后面依次進行?，F(xiàn)在我們用numk[ i ]表示第 i 位上面k 的個數(shù)，位置的序號是從低位到高位的。例如 00110這個數(shù)字，num1[ 1 ] = 0,?num1[ 2?] = 1,num1[ 3 ] = 1,?num1[ 4 ] = 0,??????? num1 5 ] = 0。
- 如果 num1[ i ] 是偶數(shù)，所以 ALice 和 Bob 這一位的結(jié)果是相等的（分析過程看下面的例子）。
- 如果 num1[ i ] 是奇數(shù)，關(guān)鍵是最后一個1花落誰家。
  - ???????當(dāng) num0[ i ] 是奇數(shù)時，那么選擇0相當(dāng)于本輪輪空。對于后手來說，如果它比先手多搶奪1個0，那它肯定贏；輸出-1
  - 當(dāng) num0[ i ] 是偶數(shù)時，只要Alice搶奪偶數(shù)個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）
由此可見前面的偶數(shù)個1
如果在Alice身上用了偶數(shù)個1，那么Bob身上肯定也用了偶數(shù)個1，偶數(shù)個1翻轉(zhuǎn)為原始值，即在這位數(shù)字上相等。
? 如果在Alice身上用了奇數(shù)個，那么Bob身上肯定也用了奇數(shù)個，兩者在該位上的1都翻轉(zhuǎn)了，所以兩者也是平局。
即關(guān)鍵是最后一個1在誰手中，誰就是贏家

3、代碼：

import java.util.Scanner;
//int類型數(shù)值范圍：2^31=10^9

public class _異或數(shù)列 {
	static int MAX_NUM = 200010;
	
	//計算每一位1的數(shù)值和所有數(shù)值的異或值
	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) {
		//如果序列的異或結(jié)果為0，那么意味著這兩個值與這些序列異或之后是相等的
		if(sum==0) {
			System.out.println(0);
			return;
		} 
		//對每一位的1進行操作，從低位開始計算，低位為1，高位為20
		for(int i=20;i>0;i--) {
			//第i位數(shù)字中所有0的個數(shù)
			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:");
		//輸入數(shù)據(jù)
		Scanner input = new Scanner(System.in);
		//定義存儲公共序列數(shù)組，其中下標(biāo)為0存儲序列個數(shù)，1-n存儲序列的值
		int [] a = new int[MAX_NUM];
		
		//輸出詢問數(shù)
		int all = input.nextInt(),sum;
		
		for(int i=0;i

參考文獻藍橋杯2021年第十二屆省賽真題-異或數(shù)列
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
            
                網(wǎng)站名稱：異或數(shù)列【博弈、位運算】-創(chuàng)新互聯(lián)
                

                新聞來源：http://m.rwnh.cn/article24/doehje.html
            
            
                成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、外貿(mào)建站、電子商務(wù)、靜態(tài)網(wǎng)站、網(wǎng)站營銷、自適應(yīng)網(wǎng)站            
            
                廣告
                
            
            
                聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：
                創(chuàng)新互聯(lián)


        
            猜你還喜歡下面的內(nèi)容
            
                
                            nagios自寫插件監(jiān)控某個程序使用物理內(nèi)存情況-創(chuàng)新互聯(lián)
                        

                            ajax局部和整體刷新的示例分析-創(chuàng)新互聯(lián)
                        

                            如何使用ajax技術(shù)無刷新動態(tài)調(diào)用新浪股票實時數(shù)據(jù)-創(chuàng)新互聯(lián)
                        

                            08r2系統(tǒng)遠程端口搞事情-創(chuàng)新互聯(lián)
                        

                            iOS調(diào)試Block引用對象無法被釋放的小技巧分享-創(chuàng)新互聯(lián)
                        

                            怎么在JavaScript中利用正則表達式對字符串中的特定字符進行獲取-創(chuàng)新互聯(lián)
                        

                            怎么在WINDOWS系統(tǒng)中搭建MYSQL環(huán)境-創(chuàng)新互聯(lián)

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

異或數(shù)列【博弈、位運算】-創(chuàng)新互聯(lián)

異或數(shù)列【博弈、位運算】-創(chuàng)新互聯(lián)