题目:给你一个n与m,再给你n个位运算操作(与、或、异或),问你初始值在0到m中能产生结果最大的数是多少
思路:
既然是位运算又要求最大,那最好的方式就是看成二进制,最后答案的二进制每一位都要尽量是1。
那么这二进制31位(32位是符号位)都是互不相关的,每个位数单独看最后是不是1就好了
首先初始的时候一个位数只可能是0或1,最后答案尽量要1
那么先直接从高位往低位枚举0和1的情况,即分两种情况,一种全部31位数都是0,一种31位数全部都是1,这两个数分别进行操作
同时要有一个数d储存初始值(防止计算的时候的初始值超出题目给的初始值)
如果这位数是0的操作完全部操作后变成1,那么答案就把这位数加上,d这位数变成0
而如果这位数原本是1,操作完之后变成1,这个时候要看d加上1所在的位数的时候是不是大于初始值,大于就不加,小于的时候就加上去,然后把d该位数变成1
整个流程中d是用来确保初始值小于m的情况,最后输出答案即可
代码如下:
#include <iostream>
using namespace std;
int main()
{
int a=0,b=0;//a是全部位数都是0的数
for(int i=0;i<31;i++){//b是全部位数都是1的数
b|=1<<i;
}
int n,m;
cin>>n>>m;
while(n--){
int t;
char s[5];
cin>>s>>t;
if(s[0]=='O'){//下面按题目要求进行三种操作
a|=t;
b|=t;
}
if(s[0]=='X'){
a^=t;
b^=t;
}
if(s[0]=='A'){
a&=t;
b&=t;
}
}
int ans=0,d=0;
for(int i=30;i>=0;i--){//从高位向低位看
if(a>>i&1){//如果在a左移i位是1就直接把答案这一位变成1
ans|=1<<i;
}else{
if(b>>i&1&&d|1<<i<m){//如果b左移i位是1并且d加上这一位的值小于初始值就把答案这一位变成1
ans|=1<<i;
d|=1<<i;//d加上初始值
}
}
}
cout<<ans;
return 0;
}

京公网安备 11010502036488号