當前位置:網站首頁>【NOI2014】15.起床困難綜合症【二進制】

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

2022-06-23 18:41:45致命小學期

題目描述:


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 分別進行 ORXOR 與 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;
} 

版權聲明
本文為[致命小學期]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/174/202206231750379541.html

隨機推薦