题目描述
有$n$扇门,每一个门有一个值和一个位运算操作。
现在让你选择一个$1..m$的初始值,使走过这些门后的结果最大。
求最大结果
输入样例
3 10
AND 5
OR 6
XOR 7
输出样例:
1
由于题目中只有$and$,$or$,$xor$这三种运算,而这三种位运算不进位,因此直接枚举每一位是填$1$还是$0$就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=1E5+5;
struct hzy{string st;int x;}a[N];
int n,m;
int f(int x,int k){
for(int i=1;i<=n;i++){
int t=(a[i].x>>x)&1;//提取出这扇门的第x位
if(a[i].st=="AND"){k&=t;}
if(a[i].st=="OR"){k|=t;}
if(a[i].st=="XOR"){k^=t;}
}
return k;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].st>>a[i].x;
int val=0,ans=0;
for(int i=29;i>=0;i--){//因为对上限有要求,因此从大到小枚举
int s0=f(i,0);//分别算出填0和1最后的值
int s1=f(i,1);
if(val+(1<<i)<=m&&s0<s1){//如果填1最后的值大而且不超过m就填1
val+=(1<<i);
ans+=(s1<<i);
}
else{
ans+=(s0<<i);
}
}
cout<<ans<<endl;
}
%%%,你的代码我贺走了。
kls,发生甚么事了?