起床困难综合症

题目大意

就是问你 中那个数在经过一系列的位运算操作后得到的答案最大

分析

那么就是可以考虑最开始每一位为 ,然后到最后是否可以变回
从高位到低位依次枚举,优先考虑从 变为 ,就是说尽可能的让这个数小一点

  • 用两个数 分别表示所有位置都为 和所有位置都为
  • 如果经过了一系列操作后, 的第 位变成了 ,这一位对最后的攻击就有 1 << i 的贡献
  • 如果经过了一系列操作后, 的第 位变成了 ,那么就得看看如果原数的这一位如果是 ,那么它是否还在最开始的区间范围内,如果还在,那么这一位也对最后的攻击有 1 << i 的贡献

那么这个的时间复杂度就是个

Code

#include <cstdio>
#include <cmath>

int Ans[2], Temp(1), Sum(0);
char Opt[2];

inline int __read()
{
    int x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

int main()
{
    int N = __read(), M = __read();
    Ans[1] = -1;
    while (N--) {
        scanf("%s", Opt);
        int T = __read();
        if (Opt[0] == 'A') Ans[0] &= T, Ans[1] &= T;
        else if(Opt[0] == 'O') Ans[0] |= T, Ans[1] |= T;
        else Ans[0] ^= T, Ans[1] ^= T;
    }
    for (int i = 1 << 30; i; i >>= 1)
        if (Ans[0] & i) Sum |= i;
        else if (Ans[1] & i &&  i <= M) Sum |= i, M ^= i;
    printf("%d\n", Sum);
}