提示
在本题中,选手需要先将数字变换为二进制后再进行计算。如果操作的两个数二进制长度不同,则在前补 0 至相同长度。
OR 为按位或运算,处理两个长度相同的二进制数,两个相应的二进制位中只要有一个为 1,则该位的结果值为 1,否则为 0。
XOR 为按位异或运算,对等长二进制模式或二进制数的每一位执行逻辑异或操作。如果两个相应的二进制位不同(相异),则该位的结果值为 1,否则该位为 0。
AND 为按位与运算,处理两个长度相同的二进制数,两个相应的二进制位都为 1,该位的结果值才为 1,否则为 0。
例如,我们将十进制数 5 与十进制数 3 分别进行 OR、XOR 与 AND 运算,可以得到如下结果:
0101 (十进制 5) 0101 (十进制 5) 0101 (十进制 5)
OR 0011 (十进制 3) XOR 0011 (十进制 3) AND 0011 (十进制 3)
= 0111 (十进制 7) = 0110 (十进制 6) = 0001 (十进制 1)
参考文献
蓝书第8页
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
pair<string,int> a[1008611];
int calc(int bit,int now){
for(int i=1;i<=n;i++){
int x=a[i].second>>bit&1;
if(a[i].first=="AND") now&=x;
else if(a[i].first=="OR") now|=x;
else now^=x;
}
return now;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
char str[5];
int x;
scanf("%s%d",str,&x);
a[i]=make_pair(str,x);
}
int val=0,ans=0;
for(int bit=29;bit>=0;bit--){
int res0=calc(bit,0);
int res1=calc(bit,1);
if(val+(1<<bit)<=m&&res0<res1){
val+=1<<bit,ans+=res1<<bit;
}else{
ans+=res0<<bit;
}
}
printf("%d",ans);
return 0;
}