题目链接：牛客 NC17857

1. 题意

选择一个初始攻击力 x，满足 0 <= x <= m。它依次通过 n 扇门，每扇门对当前攻击力执行一次 AND t、OR t 或 XOR t。

求经过所有门后能够得到的最大伤害。

注意：只有初始攻击力 x 受 m 限制，最终伤害不受 m 限制。

2. 核心观察：每个二进制位可以独立模拟

AND、OR、XOR 都是按位运算，不会产生进位。一位的输出只与这一位的输入以及各门参数的对应位有关。

因此，对于每一个第 i 位，只需要模拟两种情况：

• f0：初始攻击力这一位取 0，经过全部门后，这一位的输出。
• f1：初始攻击力这一位取 1，经过全部门后，这一位的输出。

两者都只可能是 0 或 1。

int f0 = 0, f1 = 1;

for (int j = 0; j < n; j++) {
    int bit = (doors[j].t >> i) & 1;

    if (doors[j].op == "AND") {
        f0 &= bit;
        f1 &= bit;
    } else if (doors[j].op == "OR") {
        f0 |= bit;
        f1 |= bit;
    } else { // XOR
        f0 ^= bit;
        f1 ^= bit;
    }
}

各位的门运算可以独立模拟，但输入各位的选择还需要共同满足 x <= m。

3. 为什么从高位到低位选择？

二进制第 i 位的数值是 2^i，比所有更低位的数值之和还大：

2^i > 2^i - 1 = 2^0 + 2^1 + ... + 2^(i-1)

所以在高位已经确定的前提下，应优先让当前输出位为 1。更低位的收益无法弥补当前输出位从 1 变成 0 的损失。

维护两个不同的变量：

两者初始都是 0。从高到低处理时，尚未处理的低位都暂时保持为 0。

4. 当前位怎样选择？

只有 f0 = 0, f1 = 1 时，输入位取 1 才能改善当前输出。

如果两种输入的输出一样，就选输入 0：输出没有损失，输入数值更小，给后续低位保留更多选择空间。

代码可以合并为：

if (f1 > f0 && x + (1 << i) <= m) {
    x |= (1 << i);
    ans |= (1 << i);
} else {
    ans |= (f0 << i);
}

这里的两个条件分别表示：

• f1 > f0：输入当前位取 1 能让输出更好。
• x + (1 << i) <= m：选择这一输入位后，初始攻击力仍合法。

因为第 i 位尚未处理，x 的这一位一定是 0，所以设置这一位等价于给 x 加上 2^i。

进入 else 时，输入这一位保持 0，因此输出取 f0：

ans |= (f0 << i);

如果 f0 = 0，这行不改变 ans；如果 f0 = 1，它把答案的第 i 位设为 1。

5. 位运算写法：为什么一个右移，一个左移？

读取第 i 位：右移后与 1

int bit = (t >> i) & 1;

右移将目标位移动到最低位，& 1 清除其他所有位，只保留最低位。

例如 t = 10，二进制是 1010，取第 1 位（从第 0 位开始编号）：

1010 >> 1 = 0101
0101 & 0001 = 0001

不能用 | 0 替代 & 1，因为任意整数与 0 按位或，都等于它自身，不会清除高位。

例如取 4 = 100₂ 的第 1 位，正确结果为 0：

(4 >> 1) | 0 = 2   // 没有完成取位
(4 >> 1) & 1 = 0   // 正确

没有清除的高位可能干扰后续运算；尤其非零整数转换成 bool 后会变成 true，不能把整个整数的非零误当作目标位为 1。

将第 i 位设为 1：左移后按位或

ans |= (1 << i);

1 << i 生成一个只有第 i 位为 1 的数。与它按位或，就能把答案这一位设为 1，其他位不变。

ans       = 0010
1 << 3    = 1000
按位或后  = 1010

&= 不具备把 0 改成 1 的作用。尤其变量初始为 0 时，执行 x &= (1 << i) 后仍然是 0。

6. 为什么超出 m 后不能 break？

当前高位不能选，并不意味着后面的低位不能选。

例如：

1 5
OR 0

门不改变攻击力，答案显然是 5。

如果从第 30 位开始尝试设置 x，发现 2^30 > 5 就直接 break，程序会输出 0，错过所有可选低位。

正确做法是跳过不能选的当前位，继续向下：

第 2 位：0 + 4 <= 5，选，x = 4
第 1 位：4 + 2 > 5，不选，x = 4
第 0 位：4 + 1 <= 5，选，x = 5

最好先检查是否合法，再更新 x 和 ans。如果采用先设置再检查的写法，超出时必须撤销输入位，并继续处理低位。

7. 正确性说明

假设高于第 i 位的所有决策已经确定，考虑当前位。

若 f0 = 1，选择输入 0 已能得到最好的当前输出位 1；同时输入尽可能小，不会减少低位的可行选择。

若 f0 = 0, f1 = 0，当前输出只能为 0，选择输入 0 同样保留更多低位选择。

若 f0 = 0, f1 = 1，且 x + 2^i <= m，选择输入 1 可以使当前输出从 0 变为 1。这一收益大于全部低位可能提供的收益，因此应当选择。

若 x + 2^i > m，即使所有低位都取 0，该输入仍不合法；设置低位只能让输入更大，因此当前输入位只能取 0。

每一步都在保证已经确定的高位最优的前提下，做出当前位的最优选择，并在输出相同时保留最小输入。依次处理到最低位，得到的 ans 就是最大最终伤害。

8. 完整代码

下面使用 int 保存本题的非负参数，从第 30 位到第 0 位处理，覆盖非负 32 位有符号整数的有效数值位。门的信息用动态数组保存，避免固定数组容量不足。

#include <bits/stdc++.h>
using namespace std;

struct Door {
    string op;
    int t;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<Door> doors(n);
    for (int j = 0; j < n; j++) {
        cin >> doors[j].op >> doors[j].t;
    }

    int x = 0;    // 初始攻击力，始终不超过 m
    int ans = 0;  // 最终伤害

    for (int i = 30; i >= 0; i--) {
        int f0 = 0;
        int f1 = 1;

        for (int j = 0; j < n; j++) {
            int bit = (doors[j].t >> i) & 1;

            if (doors[j].op == "AND") {
                f0 &= bit;
                f1 &= bit;
            } else if (doors[j].op == "OR") {
                f0 |= bit;
                f1 |= bit;
            } else { // XOR
                f0 ^= bit;
                f1 ^= bit;
            }
        }

        if (f1 > f0 && x + (1 << i) <= m) {
            x |= (1 << i);
            ans |= (1 << i);
        } else {
            ans |= (f0 << i);
        }
    }

    cout << ans << '\n';
    return 0;
}

9. 样例分析

3 10
AND 5
OR 6
XOR 7

各参数的二进制形式为：

5 = 101
6 = 110
7 = 111

最终结果的第 2、1 位都会先被 OR 6 设置为 1，再被 XOR 7 变成 0。更高位被 AND 5 清零，后续也不会变为 1。

第 0 位经过 AND 5、OR 6 后保持原值，再被 XOR 7 翻转。因此输入最低位为 0 时，最终伤害为 1；输入最低位为 1 时，最终伤害为 0。

选择合法的初始攻击力 x = 0 即可：

0 AND 5 = 0
0 OR 6  = 6
6 XOR 7 = 1

答案为 1。

10. 复杂度与易错点

共处理 31 个二进制位，每一位遍历全部门：时间复杂度 O(31n)，存储门信息的空间复杂度 O(n)。

• 门的下标是 j，位的编号是 i：读取参数时写 doors[j].t。
• 取位使用 (t >> i) & 1，不能使用 (t >> i) | 0。
• 设置某一位为 1 使用 |=，不能使用 &=。
• 合法条件是 <= m，因为输入允许等于 m。
• 当前位不能选时继续处理低位，不能 break。
• 最终输出 ans，无需保存“修改前的答案” last。
• 只限制初始攻击力 x，不要限制最终伤害 ans。
• 固定数组必须覆盖全部门的数量；使用 vector<Door> doors(n) 可以按输入数量分配空间。