Steven_Meng's Blog

传送门

首先，我们发现位运算和十进制的加减乘除不一样，位运算对于每一位都是独立的，而加减乘除会产生进位，在一位上的操作会影响另一位。

我们可以这样理解，对于一大堆不知道是蜃么奇奇怪怪的$And$，$Or$，$Xor$ ，我们可以算出来一个函数$f(x,pos)$（其中$x=0,1$且$f(x,pos)=0,1$），使得原数上$pos$位置的$x$，经过操作之后对应位置上一定是$f(x)$。

考虑如何计算$f(x)$，发现只要搞一个全是$1$的数和一个全是$0$的数，按照题目意思给他操作一遍，操作完的数对应到$pos$位上，一定是$f(1,pos)$和$f(0,pos)$（因为位运算每一位都是独立的）

算出来$f(x)$就好做了，我们考虑贪心，

可以由$0$变成$1$，那么肯定要变

可以由$1$变成$1$，也要变

可以由$0$变成$0$，不用变（因为$0$已经是最小的可能数了）

可以由$1$变成$0$，这样一搞反而亏本了，肯定不用变

详细细节见代码

#include <bits/stdc++.h>
#define MAXM 30
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar(); 
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
inline char gc(){
    char ch=getchar();
    while (ch!='A'&&ch!='O'&&ch!='X') ch=getchar();
    return ch;
}
int main(){
    int n=read(),m=read();
    int f1=0x7fffffff,f0=0;
    for (register int i=1;i<=n;++i){
        char opr=gc();
        int x=read();
        if (opr=='A') f0&=x,f1&=x;
        if (opr=='O') f0|=x,f1|=x;
        if (opr=='X') f0^=x,f1^=x;
    }
    int ans=0;
    for (register int i=MAXM;i>=0;--i){
        if (f0&(1<<i)){
            ans|=(1<<i);
        }
        else if ((1<<i)<=m&&(f1&(1<<i))){
            ans|=(1<<i);
            m-=(1<<i);
        }
    }
    printf("%d\n",ans);
}