形式化题目

给定 $n$ 扇防御门，每扇门是一个运算 $op_i \in \{\text{AND}, \text{OR}, \text{XOR}\}$ 与一个非负整数参数 $t_i$。 定义 $f(x)$ 为把 $x$ 依次送过所有门的结果：

求 $\max\limits_{0 \leqslant x \leqslant m} f(x)$。只需输出最大值，不需要输出取到最大值的 $x$。 按位运算的规则是：两个数前补 0 到等长后逐位计算。

样例 $n=3,\ m=10$，门依次为 AND 5、OR 6、XOR 7：

为什么偶数得 1、奇数得 0？只看最低位：$5 = 101_2$ 和 $6 = 110_2$ 的第 0 位分别是 1 和 0， 所以 AND 5、OR 6 都把 $x$ 的第 0 位原样透传；而 $7 = 111_2$ 的第 0 位是 1， XOR 7 把它翻一次：偶数 $x$ 的第 0 位是 0，翻成 1；奇数 $x$ 的第 0 位是 1，翻成 0。 更高位更简单：AND 5 把第 2 位以上全部清零，OR 6 再把第 1、2 位固定成 $11_2$， 此时值只能是 6 或 7，再经 XOR 7 后全部归零。 所以最终伤害只能取 0 或 1，最大值是 $1$。 这个样例还提示了两件事：结果既不随 $x$ 单调增长，也不总在 $x = m$ 处取到 （后者例如 $n=1$、门 AND 3、$m=4$：$f(4) = 0$，而 $f(3) = 3$ 更大），必须真的去做最大化。

正解

思路

朴素做法：枚举 $x = 0, 1, \dots, m$，每个 $x$ 依次穿过 $n$ 扇门，取最大值。 时间是 $O(nm)$：最坏 $n = 10^5$、$m = 6.6 \times 10^8$，约 $10^{13}$ 次运算，不可行。

瓶颈一：候选太多。 要枚举 $m+1$ 个 $x$，这本身就是天文数字。能不能不枚举 $x$？

关键观察：位与位互不影响。 题面规定两个数前补 0 到等长再逐位运算， AND / OR / XOR 又都是逐位运算——所以一次运算的第 $b$ 位只用到两个数的第 $b$ 位。 $n$ 扇门串起来后这条性质依旧成立：$f(x)$ 的第 $b$ 位只取决于 $x$ 的第 $b$ 位，与其他位无关。

于是 $f$ 可以按位拆开。记 $f_b(c)$ 为「输入的第 $b$ 位是 $c$ 时，输出的第 $b$ 位」，则

$B$ 位的联合决策被拆成了 $B$ 个互不相干的二元决策，未知量只剩 $f_b(0)$ 与 $f_b(1)$。

先建立一点直觉。一扇门对某一比特只有四种可能的作用，写成 $(\text{输入 }0\text{ 的输出},\ \text{输入 }1\text{ 的输出})$：

六种门按参数的一位展开就是这四种：$t$ 的该位是 0 时 AND 是恒 0、OR 与 XOR 是透传； 该位是 1 时 AND 是透传、OR 是恒 1、XOR 是取反。多扇门串起来只是这四种作用的复合， 复合结果仍落在这四种里。所以 $f_b$ 只需两个比特就能描述：$(f_b(0), f_b(1)) \in \{00, 01, 10, 11\}$—— 00 是恒 0，11 是恒 1，01 是透传，10 是取反。

瓶颈二：求 $f_b(0)$、$f_b(1)$ 还要不要 $O(nB)$？ 不用。由位独立性， $f_b(1)$ 恰好是 $f(2^b)$ 的第 $b$ 位。把所有需要用到的位同时摆成 1，一次穿越就同时得到全部 $f_b(1)$：

$lo$ 的第 $b$ 位是 $f_b(0)$，$hi$ 的第 $b$ 位是 $f_b(1)$。总共只穿越两次。

瓶颈三：$x_b$ 怎么定？ 现在目标变成最大化

这是加权最大化，高位权重大于所有低位之和（$2^b > \sum_{j<b} 2^j$）， 所以必须从高位到低位决定，高位能拿 1 就拿 1。唯一的约束是 $\sum_b x_b 2^b \leqslant m$， 用一个累加变量 a 记录已经花掉的预算即可。对第 $b$ 位：

1. 若 $lo_b = 1$：输入 0 就已经得到 1，白拿，令 $x_b = 0$，不花一分预算；
2. 否则若 $hi_b = 1$ 且 $a + 2^b \leqslant m$：花 $2^b$ 买下这一位，$a \gets a + 2^b$；
3. 否则这一位拿不到 1（$lo_b = hi_b = 0$，或预算不够），令 $x_b = 0$。

第 1 条必须排在第 2 条之前，这是全题最容易写错的一步：既然输入 0 就能拿到 1， 再花 $2^b$ 去买 1 就是纯浪费，省下的预算还能在更低位买到更多的 1。 跳过这条优先级，答案会变小——例如 $n=4$、$m=24$、门为 AND 6、OR 1、OR 27、XOR 0 时 （此时 $lo = 27$、$hi = 31$），先买高位的版本取 $x = 24$ 得 27，而正确的是 $x = 4$ 得 31。

三个瓶颈各消除一层，算法就定下来了：读入 $n$ 扇门 $\to$ 穿越两次得 $lo, hi \to$ 从高位到低位贪心。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 09:20
# update_at: 2026-10-01 09:26

import sys
from collections.abc import Callable
from operator import and_, or_, xor

type BitOp = Callable[[int, int], int]  # 一扇门的运算：把攻击力与参数 t 按位合成
type Door = tuple[BitOp, int]           # 一扇门 = 运算 + 参数

OPS: dict[bytes, BitOp] = {b'AND': and_, b'OR': or_, b'XOR': xor}


def fold(doors: list[Door], x: int) -> int:
    """把攻击力 x 依次送过所有防御门，返回最终伤害。"""
    for op, t in doors:
        x = op(x, t)
    return x


def best_attack(lo: int, hi: int, m: int) -> int:
    """在 0..m 中选初始攻击力，返回最大伤害。

    lo = f(0)、hi = f(2^B-1)，它们的第 b 位就是第 b 位输入 0 / 输入 1 的输出。
    从高位往低位贪心：输入 0 就有 1 的位白拿，否则预算够且买得到 1 才买。
    """
    ans = a = 0  # ans = 最终伤害；a = 已花掉的预算（构造中的初始攻击力，低位暂为 0）
    for bit in range(max(lo, hi, m).bit_length() - 1, -1, -1):
        free = lo >> bit & 1                    # 输入 0 就已经是 1：白拿，不花预算
        affordable = a + (1 << bit) <= m        # 这一位还买得起吗（高位已定，低位尚为 0）
        buy = not free and affordable and hi >> bit & 1  # 花钱能买到 1 才花，否则放弃
        ans |= (free or buy) << bit             # free / buy 都是真值，位移后就是这一位的值
        a += buy << bit                         # 只有真花钱时才抬高初始攻击力
    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, m = int(next(data)), int(next(data))
    doors: list[Door] = [(OPS[next(data)], int(next(data))) for _ in range(n)]

    # 每扇门都是逐位运算，某一位的输出只取决于输入的同一位。于是把 x 的所有位一起摆 1，
    # 一次穿越就同时拿到「每位输入 1 的结果」hi；输入 0 的 lo 同理，两次穿越即可。
    top = max(m, max((t for _op, t in doors), default=0)).bit_length()  # 需要决定的位数
    lo, hi = fold(doors, 0), fold(doors, (1 << top) - 1)

    print(best_attack(lo, hi, m))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:35
 * update_at: 2026-10-06 13:35
 */
#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // n 最大约 1e5
const int OP_AND = 0;    // 门运算的编号
const int OP_OR = 1;
const int OP_XOR = 2;

int n;        // 防御门数量
ll m;         // 初始攻击力的上限
int door_op[MAXN]; // door_op[i]：第 i 扇门的运算编号
ll door_t[MAXN];   // door_t[i]：第 i 扇门的参数 t

// 把攻击力 x 依次送过所有 n 扇门，返回最终伤害。
ll apply_doors(ll x) {
    for (int i = 0; i < n; i++) {
        if (door_op[i] == OP_AND) {
            x = x & door_t[i];
        } else if (door_op[i] == OP_OR) {
            x = x | door_t[i];
        } else {
            x = x ^ door_t[i];
        }
    }
    return x;
}

void read_input() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        char op[8];
        cin >> op >> door_t[i];
        if (strcmp(op, "AND") == 0) {
            door_op[i] = OP_AND;
        } else if (strcmp(op, "OR") == 0) {
            door_op[i] = OP_OR;
        } else {
            door_op[i] = OP_XOR;
        }
    }
}

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

    read_input();

    // 每扇门都是逐位运算，某一位的输出只取决于输入的同一位。把所有需要决定的位一起摆 1，
    // 一次穿越就同时得到「每位输入 1 的结果」hi；输入 0 的 lo 同理，两次穿越即可。
    ll max_val = m;
    for (int i = 0; i < n; i++) {
        if (door_t[i] > max_val) {
            max_val = door_t[i];
        }
    }
    int top = 0; // 需要决定的位数
    while ((1LL << top) <= max_val) {
        top++;
    }

    ll lo = apply_doors(0);                       // 第 b 位 = 该位输入 0 时的输出
    ll hi = apply_doors((1LL << top) - 1);        // 第 b 位 = 该位输入 1 时的输出

    // 从高位到低位贪心：输入 0 就是 1 的位白拿；否则预算够且花钱能买到 1 才买。
    ll ans = 0;  // 最终最大伤害
    ll used = 0; // 已花掉的预算（即构造中的初始攻击力）
    for (int b = top - 1; b >= 0; b--) {
        ll w = 1LL << b;
        int lo_bit = (lo >> b) & 1;
        int hi_bit = (hi >> b) & 1;
        if (lo_bit == 1) {
            ans |= w;
        } else if (hi_bit == 1 && used + w <= m) {
            ans |= w;
            used += w;
        }
    }

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

复杂度

空间 $O(n)$，用于存 $n$ 扇门。最大数据（$n = 92647$、$m = 665522854$）实测约 0.04 s、峰值 36 MB， 远低于 1000 ms / 128 MB 的限制。

总结

本题的核心只有两句话：

1. 按位独立：AND / OR / XOR 逐位运算，所以 $f$ 的每一位只由 $x$ 的同一位决定， $m+1$ 个候选取值根本不必枚举；把所有位一起摆 1（再摆 0）穿越两次，就能一次性测出全部位的性质。
2. 高位优先贪心：位权 $2^b$ 大于所有低位权重之和，所以从高位往低位能拿就拿， 但要先用累计预算 a 检查 $a + 2^b \leqslant m$；输入 0 就能拿到的位免费，绝不为它花钱。

这是一个「$O(nm)$ 枚举 $\to$ $O(n + \log)$ 贪心」的典型转化：先用量词结构（按位独立）砍掉候选集合， 再用权重结构（二进制位权）砍掉搜索顺序。

图示解析

下面这张表把样例 $n=3, m=10$（门 AND 5、OR 6、XOR 7）的贪心决策逐步摊开， 展示 $lo$、$hi$ 与每一步的预算变化。

$B = \max(10, 7)$ 的位长 $= 4$，所以处理第 3 位到第 0 位。两次穿越得到 $lo = f(0) = 1 = 0001_2$（各位输入 0 的结果），$hi = f(15) = 0 = 0000_2$（各位输入 1 的结果）：

贪心构造出的 $x = 0$，伤害 $f(0) = 1$，与枚举得到的最大值一致。 观察重点有两个：一是四位里只有第 0 位有机会，其余位在 $lo$ 和 $hi$ 中都是 0，说明它们被门强制清零了； 二是第 0 位是「白拿」的——输入 0 就有 1，因此不需要动预算，这也说明了为什么 free 必须优先于 buy。