算法競賽進階指南0x00基本算法 0x01位運算 例題起床困難綜合征

題目

21 世紀，許多人得了一種奇怪的病：起床困難綜合症，其臨床表現為：起床難，起床後精神不佳。

作為一名青春陽光好少年，atm 一直堅持與起床困難綜合症作鬥争。

通過研究相關文獻，他找到了該病的發病原因： 在深邃的太平洋海底中，出現了一條名為 drd 的巨龍，它掌握着睡眠之精髓，能随意延長大家的睡眠時間。

正是由于 drd 的活動，起床困難綜合症愈演愈烈， 以驚人的速度在世界上傳播。

為了徹底消滅這種病，atm 決定前往海底，消滅這條惡龍。

曆經千辛萬苦，atm 終于來到了 drd 所在的地方，準備與其展開艱苦卓絕的戰鬥。

drd 有着十分特殊的技能，他的防禦戰線能夠使用一定的運算來改變他受到的傷害。

具體說來，drd 的防禦戰線由 n 扇防禦門組成。

每扇防禦門包括一個運算 op 和一個參數 t，其中運算一定是 OR,XOR,AND 中的一種，參數則一定為非負整數。

如果還未通過防禦門時攻擊力為 x，則其通過這扇防禦門後攻擊力将變為 x op t。

最終 drd 受到的傷害為對方初始攻擊力 x 依次經過所有 n 扇防禦門後轉變得到的攻擊力。

由于 atm 水準有限，他的初始攻擊力隻能為 0 到 m 之間的一個整數（即他的初始攻擊力隻能在 0,1,…,m 中任選，但在通過防禦門之後的攻擊力不受 m 的限制）。

為了節省體力，他希望通過選擇合适的初始攻擊力使得他的攻擊能讓 drd 受到最大的傷害，請你幫他計算一下，他的一次攻擊最多能使 drd 受到多少傷害。

輸入格式

第 1 行包含 2 個整數，依次為 n,m，表示 drd 有 n 扇防禦門，atm 的初始攻擊力為 0 到 m 之間的整數。

接下來 n 行，依次表示每一扇防禦門。每行包括一個字元串 op 和一個非負整數 t，兩者由一個空格隔開，且 op 在前，t 在後，op 表示該防禦門所對應的操作，t 表示對應的參數。

輸出格式

輸出一個整數，表示 atm 的一次攻擊最多使 drd 受到多少傷害。

資料範圍

輸入樣例：

3 10

AND 5

OR 6

XOR 7

輸出樣例：

1

樣例解釋

atm可以選擇的初始攻擊力為 0,1,…,10。

假設初始攻擊力為 4，最終攻擊力經過了如下計算

4 AND 5 = 4

4 OR 6 = 6

6 XOR 7 = 1

類似的，我們可以計算出初始攻擊力為 1,3,5,7,9 時最終攻擊力為 0，初始攻擊力為 0,2,4,6,8,10 時最終攻擊力為 1，是以 atm 的一次攻擊最多使 drd 受到的傷害值為 1。

運算解釋

在本題中，選手需要先将數字變換為二進制後再進行計算。如果操作的兩個數二進制長度不同，則在前補 0 至相同長度。

OR 為按位或運算，處理兩個長度相同的二進制數，兩個相應的二進制位中隻要有一個為 1，則該位的結果值為 1，否則為 0。

XOR 為按位異或運算，對等長二進制模式或二進制數的每一位執行邏輯異或操作。如果兩個相應的二進制位不同（相異），則該位的結果值為 1，否則該位為 0。

AND 為按位與運算，處理兩個長度相同的二進制數，兩個相應的二進制位都為 1，該位的結果值才為 1，否則為 0。

例如，我們将十進制數 5 與十進制數 3 分别進行 OR、XOR 與 AND 運算，可以得到如下結果：

0101 (十進制 5)             0101 (十進制 5)             0101 (十進制 5)             
OR 0011 (十進制 3)         XOR 0011 (十進制 3)         AND 0011 (十進制 3)             
=  0111 (十進制 7)           = 0110 (十進制 6)           = 0001 (十進制 1)  
           

解答

各二進制位運算結果是獨立無關的，不涉及進位，與其他位無關，隻考慮填0或1
由高位往低位填10^9約小于2^30，用最高位為29
第k位填1，當且僅當滿足以下兩個條件：
1.已填好的最高位所構成的數+(1<<k)<=m
2.第k位為0，經過n次操作後，算出來的值res0<第k位為1，經過n次操作後，算出來的值res1.否則填1還不如填0優
           

import java.util.Scanner;

public class Main {
	static int n;
	static String[] symble;//操作
	static int[] number;//參數
public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();//n個門
		int m=sc.nextInt();//範圍0~m
		symble=new String[n];
		number=new int[n];
		for (int i = 0; i < n; i++) {
			symble[i]=sc.next();
			number[i]=sc.nextInt();
		}
		int val=0;//當下的初始攻擊力
		int ans=0;//最終攻擊力
		//10^9約小于2^30,bit從29開始
		for (int bit = 29; bit >= 0; bit--) {
			int res0=f(bit,0);
			int res1=f(bit,1);
			if(val+(1<<bit)<=m && res0<res1) {
				//第bit位為1
				val+=(1<<bit);
				ans+=res1<<bit;
			}else {
				//第bit位為0
				ans+=res0<<bit;
			}
		}
		System.out.println(ans);
	}
	private static int f(int bit, int num) {
		//num為0或者1
		for (int i = 0; i < n; i++) {
			int bit_num=number[i]>>bit&1;
			if(symble[i].equals("AND")) {//這裡必須用.equels不能用==
				num&=bit_num;
			}else if(symble[i].equals("OR")) {
				num|=bit_num;
			}else {//"XOR"
				num^=bit_num;
			}
		}
		return num;
	}
}