AcWing 998. 起床困难综合症

原题链接

?

其实上面这一堆就是想说，输入 n,m以及 n 个数和该数所对应的运算，其中运算包括有 与、或、异或 三种，真正的问题就是在所有不大于 m 的数（非负数）中，对给定的 n 个数都按该数所对应的运算运算一遍后，能得到得最大的值是多少。

AND 表示按位与，OR 表示按位或，XOR 表示按位异或
?

?Accepted Code：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=1e6+5;
int n,m;	//门的数量以及攻击力 
int t[N];	//运算的参数 
char str[4];	//存储输入的字符串 
int op[N];	//存储运算操作 
int ans;	//存储答案 
 
bool calc(bool x,int j) {
	for(int i=0;i<n;i++){
		if(op[i] == 1) x&=t[i]>>j&1; 
		else if(op[i] == 2) x|=t[i]>>j&1;
		else x^=t[i]>>j&1;
	}
	return x;
}//function：执行各种运算（
 
/*  因为该题的按位与、按位或、按位异或的每次运算只有关该位上的数字，不影响其他位置上的数字
    又因为C语言的结构特点我们可以从高位到低位来确定数的每一位*/
int main(){
	scanf("%d %d",&n,&m);
	
	for(int i=0;i<n;i++){
		scanf("\n%s %d",str,t+i);
		
        /*标记成整数形方便后续对应是什么运算*/
		if(*str=='A') op[i]=1;	//与运算 
		else if(*str=='O') op[i]=2;	  //或运算 
		else op[i]=3;	//异或运算 
	}
	
	for(int i=29;~i;i--){ 
		if(1<<i<=m){	//伤害不能超出范围 
			bool x=calc(0,i);   //该位填0的结果
			bool y=calc(1,i);   //该位填1的结果
            //哪个数值更大就填哪个
			if(x>=y)	ans|=x<<i;
			else ans|=y<<i,m-=1<<i; //(填1的话要让m减去该结果，为了后续只需要继续小等于m)
		}
		else ans|=calc(0,i)<<i; //超出范围了只能将该位置置为0
	}
	
	cout<<ans<<endl;
	
	return 0;
}