前言

太菜了，参考了大佬的思路。

题意

给定一些位运算操作，对于[0,m]中的整数，求经过运算后的最大值。

解题思路

先考虑暴力怎么做，对于[0,m]中的每一个数，分别计算他们经过运算后的值，取最大值。复杂度O(mn),显然会超时。
发现按位与，按位或，异或这种位运算，对于一个二进制位，只会影响其本身，而不会影响其他二进制位。可以将问题转化到二进制位上，对于每个二进制位经过运算后为0，还是为1；当然我们希望它为1。
我们从高到低枚举每一位，若该位选1不会超过m，则说明该位可选1也可选0，计算一下选1和选0经过运算后的值，取最大的。
若该位选1会超过m，则该位只能选0。
这样每一位运算一遍，复杂度O(nlogm)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    string s;
    int x;
}a[100010];
int n;
int calc(int x,int k){
    for(int i=1;i<=n;i++){
        if(a[i].s[0]=='A') x&=a[i].x>>k;
        if(a[i].s[0]=='O') x|=a[i].x>>k;
        if(a[i].s[0]=='X') x^=a[i].x>>k;
    }
    return x;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i].s>>a[i].x;
    int ans=0,cnt=0;  //cnt表示所选的[0,m]中的数
    for(int i=29;i>=0;i--){
        //该位可以选1
        if(cnt+(1<<i)<=m){
            int x=calc(1,i),y=calc(0,i); //计算选1和选0的贡献
            if(x>y){
                ans|=x<<i; cnt+=(1<<i);
            }
            else ans|=y<<i;
        }
        else ans|=calc(0,i)<<i;  //该位只能选0
    }
    cout<<ans<<endl;
    return 0;
}