位运算每一位都有独立性,因此按位枚举。
由于高位取1一定比低位取1大,因此从高位向低位枚举,尽量让当前位最终的值取1,
枚举当前位取0/1时最终这一位的取值,若当前位取1不优于取0,则取0.否则取1。
可以发现,$log_2m<30$,因此从第29位枚举即可,时间复杂度$O(n\log m)$。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int opt[N],a[N];
bool get(bool pre,int wei){
for(int i=1;i<=n;i++){
bool sum=(a[i]>>wei)&1;
if(opt[i]==1)pre|=sum;
else if(opt[i]==2)pre^=sum;
else pre&=sum;
}
return pre;
}
int ans;
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
string s;
cin >> s >> a[i];
if(s=="OR")opt[i]=1;
else if(s=="XOR")opt[i]=2;
else opt[i]=3;
}
for(int i=29;i>=0;i--){
if(m>=(1<<i)){
bool x=get(1,i),y=get(0,i);
if(y>=x)ans+=y<<i;
else ans+=x<<i,m-=x<<i;
}
else{
ans+=get(0,i)<<i;
}
}
cout << ans;
return 0;
}
另一种实现:
定义两个数$(000…000)_2,(111…111)_2$,输入每个操作时对这两个数进行操作,这样枚举每位时直接比较这两个数当前位的值即可,第一个数等价于当前位取0,第二个等价于当前位取1。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int x=0,y=(1<<30)-1;
int ans;
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
string s;
int t;
cin >> s >> t;
if(s=="OR")x|=t,y|=t;
else if(s=="XOR")x^=t,y^=t;
else x&=t,y&=t;
}
for(int i=29;i>=0;i--){
bool s0=(x>>i)&1,s1=(y>>i)&1;
if(m>=(1<<i)){
if(s0>=s1)ans+=s0<<i;
else ans+=s1<<i,m-=s1<<i;
}
else{
ans+=s0<<i;
}
}
cout << ans;
return 0;
}