[noi 2014] 15. Syndrome de difficulté à se lever [binaire]

Description du sujet：

drdLe Front défensif denComposition des portes de défense.Chaque porte de défense contient une opérationopEt un paramètret,Où l'opération doit êtreOR,XOR,ANDUn des,Le paramètre doit être un entier non négatif.Si l'attaque n'a pas encore franchi la porte de défensex,Et sa puissance d'attaque passera àx op t.FinaldrdLes dégâts sont la force d'attaque initiale de l'adversairexPasser par tous lesnLa puissance d'attaque générée par la transition derrière la porte de défense.Parce queatmNiveau limité,Son attaque initiale ne peut être que0ÀmUn entier entre（C'est - à - dire que sa force d'attaque initiale ne peut être que 0, 1, … , mOption moyenne,Mais la force d'attaque après avoir franchi la porte de défense n'est pasmLimites）.Pour économiser de l'énergie,Il espère qu'en choisissant la bonne force d'attaque initiale, son attaque permettradrdLes plus grands dégâts,S'il vous plaît, aidez - le à calculer,Au mieux, une de ses attaquesdrdCombien de dégâts.
 

Format d'entrée：

Fichier d'entrée 1 Ligne contenant 2 Nombre entier,Dans l'ordren, m,Représentation drd Oui.nPortes de défense,atm La puissance d'attaque initiale de0ÀmEntier entre.
Et puis...nD'accord,Chaque porte de défense à son tour.Chaque ligne contient une chaîneopEt un entier non négatift,Les deux sont séparés par un espace,EtopAvant,tÀ l'arrière.,opIndique le fonctionnement correspondant de la porte de défense,tReprésente le paramètre correspondant.

Format de sortie：

Sortie d'un entier ligne par ligne,ReprésentationatmUne attaque dedrdCombien de dégâts.

Exemple：

Exemple1Entrée

3 10
AND 5
OR 6
XOR 7

Exemple1Produits

1

Exemple1Explication：
Supposons que la force d'attaque initiale soit 4, La force d'attaque finale a été calculée comme suit ：

4 AND 5 = 4
4 OR 6 = 6
6 XOR 7 = 1

Similaire, On peut calculer que la force d'attaque initiale est 1,3,5,7,9 La puissance d'attaque finale est 0,L'attaque initiale est 0,2,4,6,8,10 La puissance d'attaque finale est 1,Donc,atmUne attaque dedrd La valeur des dommages subis est 1.

Champ d'application des données

Dans cette question, Le candidat doit d'abord convertir les nombres en binaires avant d'effectuer le calcul . .Si la longueur binaire des deux nombres de l'opération est différente , Avant de compléter  00  Même longueur .

• OR  Pour les bits ou les opérations ,Traiter deux nombres binaires de même longueur,Un seul des deux bits binaires correspondants est 1,La valeur résultante de ce bit est 1,Sinon 0.
• XOR  Pour les opérations Xor bitwise , Effectuer une exclusion logique ou une opération sur chaque bit d'un mode binaire de longueur égale ou d'un nombre binaire . Si les deux bits binaires correspondants sont différents （Différences）,La valeur résultante de ce bit est 1,Sinon, ce bit est 0.
• AND  Pour les bits et les opérations ,Traiter deux nombres binaires de même longueur, Les deux bits binaires correspondants sont 1,La valeur résultante de ce bit est 1,Sinon 0.

Par exemple, On va prendre les décimales  5 Et le nombre décimal 3 Faites - le séparément. OR、XOR Avec AND Opération,Les résultats suivants peuvent être obtenus：

    0101 (Décimal 5)
 OR 0011 (Décimal 3)
  = 0111 (Décimal 7)

    0101 (Décimal 5)
XOR 0011 (Décimal 3)
  = 0110 (Décimal 6)

    0101 (Décimal 5)
AND 0011 (Décimal 3)
  = 0001 (Décimal 1)

Solution 1：

Convertir en nombre binaire,énumérez chaque bit, Regarde ça. 0 Toujours 1Heure Peut faire passer n À la porte 1 . 

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

typedef long long ll;

const int N=1e5+10;// Valeur maximale de la porte  
ll ans,power[N];//La réponse , Tableau des poids 
int n,m,t[N];//nLa porte.  0-mAttaque initiale Nombre entré 
int op[N];//Opérateur entré 

bool fun(int i,int now)//iEst le nombre de chiffres 
{
	int temp;
	for(int j=1;j<=n;j++)//nPortes 
	{
		temp =1 & (t[j]>>i);//Enlevez - le.t[j] Les premiers chiffres de  De0C'est parti. 
		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;//Entrez la porte Et Puissance d'attaque maximale 
	//Entrez le numéro 
	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;
	}
	//Tableau des poids
	power[0]=1;
	for(int i=1;i<=31;i++)
	{
		power[i]=power[i-1]*2;//Poids 
	} 
	
	for(int i=31;i>=0;i--)
	{
		if( fun(i,0) )//NoiBits - Oui.0,En passantN La porte est devenue 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;
}