?
其实上面这一堆就是想说,输入 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;
}