【NOI2014】15.起床困難綜合症【二進制】

題目描述：

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受到多少傷害。

樣例：

樣例1輸入

3 10
AND 5
OR 6
XOR 7

樣例1輸出

1

樣例1解釋：
假設初始攻擊力為 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。

數據範圍

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

• OR 為按比特或運算，處理兩個長度相同的二進制數，兩個相應的二進制比特中只要有一個為 1，則該比特的結果值為 1，否則為 0。
• XOR 為按比特异或運算，對等長二進制模式或二進制數的每一比特執行邏輯异或操作。如果兩個相應的二進制比特不同（相异），則該比特的結果值為 1，否則該比特為 0。
• AND 為按比特與運算，處理兩個長度相同的二進制數，兩個相應的二進制比特都為 1，該比特的結果值才為 1，否則為 0。

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

    0101 (十進制 5)
 OR 0011 (十進制 3)
  = 0111 (十進制 7)

    0101 (十進制 5)
XOR 0011 (十進制 3)
  = 0110 (十進制 6)

    0101 (十進制 5)
AND 0011 (十進制 3)
  = 0001 (十進制 1)

解法一：

轉化為二進制數，枚舉每一比特，看它為0 還是 1時 可以使經過n扇門時為1 。 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e5+10;//門的最大值 
ll ans,power[N];//答案 ， 權值數組 
int n,m,t[N];//n扇門  0-m初始攻擊力 輸入的數字 
int op[N];//輸入的運算符 

bool fun(int i,int now)//i是比特數 
{
	int temp;
	for(int j=1;j<=n;j++)//n門 
	{
		temp =1 & (t[j]>>i);//取出t[j]的第幾比特數字 從0開始 
		if(op[j]==1)now=now&temp;
		else if(op[j]==2)now=now|temp;
		else now=now^temp;
	}
	return now;
}

int main()
{
	cin>>n>>m;//輸入門 和 最大攻擊力 
	//輸入數字 
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s>>t[i];
		if(s[0]=='A')op[i]=1;
		else if(s[0]=='O')op[i]=2;
		else op[i]=3;
	}
	//權值數組
	power[0]=1;
	for(int i=1;i<=31;i++)
	{
		power[i]=power[i-1]*2;//權重 
	} 
	
	for(int i=31;i>=0;i--)
	{
		if( fun(i,0) )//第i比特 是0，在經過N道門之後變成1  
		{	
			ans += power[i];
			cout<<ans<<endl;	
		}
		else if(m>power[i] && fun(i,1)) 
		{
			ans += power[i],m-=power[i];
			cout<<ans<<endl;
		}	
	}
	cout<<ans;
	
	return 0;
}