Solution

考虑位运算的特点：不进位。

于是可以将答案的每一位分开考虑。从高位到低位枚举每一位所选的 情况。若当前位第 位经过一系列运算后结果可以为 ，那就将答案加上 。由于枚举时由高到低，贪心地使高位为 即可（第 位贡献的答案比第 位到第 位贡献的和还要多）。注意累加值不超过 。

Code

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1e5+10;
struct node{
    string op;
    int t;
}a[maxn];
int n,m,sum,ans;
int fr(){
    char ch=getchar();
    while(ch>'9'||ch<'0')
        ch=getchar();
    int sum=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        sum=(sum<<3)+(sum<<1)+ch-'0';
    return sum;
}
int check(int x,int y){
    int z;
    for(int i=1;i<=n;i++){
        z=a[i].t>>y&1;
        if(a[i].op=="AND")
            x&=z;
        else if(a[i].op=="OR")
            x|=z;
        else
            x^=z;
    }
    return x;
}
int main(){
    n=fr(); m=fr();
    for(int i=1;i<=n;i++){
        cin>>a[i].op;
        a[i].t=fr();
    }
    int x,y;
    for(int i=29;i>=0;i--){
        x=check(1,i);
        y=check(0,i);
        if(x>y&&sum+(1<<i)<=m){
            sum+=(1<<i);
            ans+=(x<<i);
        }
        else
            ans+=(y<<i);
    }
    printf("%d",ans);
    return 0;
}