最大值

GitHub跳转原题关系图返回列表

按算子分治:与用逐位贪心加超集计数,异或用 0-1 Trie 求最大异或对,或用值域超集变换加逐位贪心,三者都是 O(20n) 级。

OJ: roj

题目 ID: 1776

难度:提高+/省选-

标签:位运算字典树动态规划贪心python

创建: 2026-10-08 02:12

更新: 2026-10-08 02:12

形式化题目

给定长度为 nn 的正整数序列 A1,A2,…,AnA_1, A_2, \dots, A_n(1⩽Ai<2201 \leqslant A_i < 2^{20})和一个算子的 编号 cc,求

max⁡1⩽i<j⩽n(AiopAj),op={按位与c=1按位异或c=2按位或c=3 \max_{1 \leqslant i < j \leqslant n} (A_i \mathbin{op} A_j), \qquad op = \begin{cases} \text{按位与} & c = 1\\ \text{按位异或} & c = 2\\ \text{按位或} & c = 3 \end{cases}

多组数据:第一行 TT,之后每组两行(n c 与 nn 个整数),每组输出一行答案。 范围 T⩽6T \leqslant 6,2⩽n⩽1052 \leqslant n \leqslant 10^5,单组时限 1500 ms、内存 128 MB。

需要注意算子的编号顺序与直觉不同:c=2c = 2 是异或、c=3c = 3 才是或,误记会直接错。

朴素做法枚举 (n2)\binom{n}{2} 个数对,单组 O(n2)O(n^2),n=105n = 10^5 时是 5×1095 \times 10^9 次位运算, 必然超时。突破口在于 Ai<220A_i < 2^{20}:二进制位数 B=20B = 20 很小、值域 2202^{20} 有限, 所以可以围绕"位"而不是围绕"数对"来设计算法。三个算子的性质各不相同,分开处理。

正解

思路

情形 c=1c = 1:按位与

按位与"同为 1 才为 1",所以答案掩码的每一位都要求至少两个数在该位上同时为 1。 更一般地,对任意候选掩码 cand\text{cand}:

存在 i≠ji \neq j 使 (Aiand⁡Aj)⊇cand(A_i \operatorname{and} A_j) \supseteq \text{cand}   ⟺  \iff 至少两个下标满足 cand⊆Ak\text{cand} \subseteq A_k(即 Akand⁡cand=candA_k \operatorname{and} \text{cand} = \text{cand})。

必要性显然;充分性同样显然:取这两个元素配对,它们的 AND 含 cand\text{cand} 的全部 1。

这条性质对 cand\text{cand} 是单调的:把 cand\text{cand} 的某位清零只会让条件更容易成立。 于是可以套标准的"从高位到低位贪心构造答案":设已确定的高位集合为 curcur, 尝试把第 bb 位置 1 得到 cand=cur∣2b\text{cand} = cur \mid 2^b,若可行就保留这一位。单调性保证 贪心不会因为先前选错了高位而错过更优解——这正是 01-Trie 之上、更朴素的"逐位确定"套路。

可行性判定就是数一数有多少个 AkA_k 含 cand\text{cand},扫一遍序列、数到 2 就收工:

ans1=贪心结果,每轮 O(n) ans_1 = \text{贪心结果}, \qquad \text{每轮 } O(n)

单组共 O(Bn)≈2×106O(Bn) \approx 2 \times 10^6 次操作,非常轻。

情形 c=2c = 2:按位异或

异或"相异为 1",是和"前缀相同/相异"绑定最深的一种运算,标准做法是 0-1 Trie(二进制字典树): 把数按二进制从高位到低位插入,形成一棵深度 BB 的二叉树,每个节点对应一个二进制前缀。 查询 AiA_i 时从根往下走,若第 bb 位想走的分支(与 AiA_i 的第 bb 位相反)存在, 就走过去并把答案的第 bb 位置 1,否则被迫走另一分支。这样按高位优先的顺序, 每步都做了"这一步能挣的最大值"的最优选择,得到的即是与 AiA_i 异或最大的元素。

要让 i≠ji \neq j,只需边查询边插入:对第 ii 个数先查询(此时树上只有 A1…Ai−1A_1 \dots A_{i-1}), 再插入 AiA_i。这样树上任何一次查询匹配到的必然是不同下标,无需额外过滤, 也无"自己和自己异或得 0"的干扰。

单组复杂度 O(Bn)O(Bn),Trie 节点数 ⩽Bn≈2×106\leqslant Bn \approx 2 \times 10^6。

情形 c=3c = 3:按位或

或运算的单调性方向与与运算一致(或的结果只增不减),所以仍可逐位贪心:

存在 i≠ji \neq j 使 (Aior⁡Aj)⊇cand(A_i \operatorname{or} A_j) \supseteq \text{cand}   ⟺  \iff 存在某个下标 ii,使 cand\text{cand} 中 AiA_i 缺的那些位能被另一个元素补齐。

记 ti=candand⁡¬Ait_i = \text{cand} \operatorname{and} \lnot A_i(AiA_i 在 cand\text{cand} 上缺的位),则条件等价于 “存在 ii,使某个元素包含 tit_i(即 ti⊆Ajt_i \subseteq A_j)”。两个要点:

  1. tit_i 与 AiA_i 的位完全不相交(tit_i 只取 AiA_i 为 0 的位),所以 ti≠0t_i \neq 0 时, 包含 tit_i 的那个元素一定不是 AiA_i 自己,自匹配天然被排除;
  2. ti=0t_i = 0 时 AiA_i 自己就覆盖了整个 cand\text{cand},任取另一个下标即可,题面保证 n⩾2n \geqslant 2。

于是只需要一张"是否存在元素包含掩码 mm"的查询表。这正是 SOS DP(高维后缀和) 的经典场景:设 f[m]=1f[m] = 1 当且仅当值 mm 出现过,按位做

f[m]←f[m]  or  f[m∣2b](m 的第 b 位为 0)f[m] \leftarrow f[m] \;\text{or}\; f[m \mid 2^b] \qquad (m \text{ 的第 } b \text{ 位为 } 0)

一遍之后 f[m]f[m] 就表示"是否存在元素是 mm 的超集"。预处理 O(B⋅2B)O(B \cdot 2^B), 之后每一位判定只需扫 nn 个元素、每个元素一次 O(1)O(1) 查表,贪心本身 O(Bn)O(Bn)。

flowchart TD
    A["统计出现过的值<br/>f[v] = 1"] --> B["按位 b = 0..19<br/>f[m] |= f[m | 2^b]"]
    B --> C["超集表:f[m] = 是否存在元素 ⊇ m"]
    C --> D["逐位贪心 cand = cur | 2^b"]
    D --> E["扫 n 个元素:查 f[cand & ~A_i]"]
    E -->|"存在为 1"| F["保留第 b 位"]
    E -->|"全为 0"| G["舍弃第 b 位"]

一个必须避开的错解。 容易想当然地认为"或的最大值一定由最大值和次大值配对得到", 这是错的。反例 A={10,5,12}A = \{10, 5, 12\}:最大值 1212 与次大值 1010 得 12or⁡10=1412 \operatorname{or} 10 = 14, 而 10or⁡5=1510 \operatorname{or} 5 = 15 更大——恰是"把高位的 1 让出去、换来低位全 1"更划算。 测试数据第 5 组专门放了这组定向反例。所以必须老老实实做逐位贪心(或等价地枚举每个元素 作为一端再贪心另一半),不能只看最大两个数。

代码

C++ 逐算子实现(与运算逐位贪心、异或走 0-1 Trie、或用 SOS + 贪心):

cpp
/**
 * 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-08 02:12
 * update_at: 2026-10-08 02:12
 */

// 一本通 1776《最大值》
// 每组数据给定序列 A 与算子 c(1=and, 2=xor, 3=or),求 max_{i<j} (A_i op A_j)。
// 三个算子各用一种经典做法:
//   c=1 与:逐位贪心,判定“至少 2 个元素包含候选掩码”
//   c=2 异或:0-1 Trie 求最大异或对
//   c=3 或:值域超集(SOS)预处理 + 逐位贪心
#include <cstdio>
#include <cstring>

// 题目数据默认 ll;这里的数组元素都是 < 2^20 的位掩码,用 int 更省内存、位运算更直接
typedef long long ll;

static const int MAXN = 100000 + 5;   // n 上限
static const int MAXB = 20;           // 题面保证 A_i < 2^20
static const int DOM = 1 << MAXB;     // 值域大小 2^20
static const int MAXNODE = MAXN * MAXB + 5;  // Trie 节点上限:每个数 20 层

static int a[MAXN];                   // 当前这组数据的序列,a[i] 是位掩码

// sup[m] != 0 表示序列中存在某个元素包含 m 的全部二进制 1(即 m 是它的子掩码)
static unsigned char sup[DOM];

// Trie 节点:两个孩子(bit=0 / bit=1)
struct TrieNode {
    int child[2];
};

// 动态化静态:TrieNode 数组 + trie_cnt 当分配指针,开点由 new_node 负责
static TrieNode trie[MAXNODE];
static int trie_cnt;

// 开一个新 Trie 节点,返回它的编号
static int new_node(void) {
    trie_cnt++;
    trie[trie_cnt].child[0] = 0;
    trie[trie_cnt].child[1] = 0;
    return trie_cnt;
}

// 取 mx 的最高二进制位编号(mx >= 1)
static int hi_bit(int mx) {
    int h = 0;
    while ((mx >> (h + 1)) != 0) h++;
    return h;
}

// c=1 与运算:从高位到低位贪心。
// 若存在至少 2 个元素都包含候选掩码 cand,则两位元素的 AND 就能保住 cand,
// 这一位可取;谓词“存在一对数使 AND 包含 cand”对 cand 的下降单调,故贪心正确。
static int solve_and(int n, int hi) {
    int cur = 0;
    for (int b = hi; b >= 0; b--) {
        int cand = cur | (1 << b);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if ((a[i] & cand) == cand) {
                cnt++;
                if (cnt >= 2) break;   // 够两个就不必再数
            }
        }
        if (cnt >= 2) cur = cand;
    }
    return cur;
}

// c=2 异或运算:把序列依次插入 0-1 Trie,每个数插入前先查询它与“已插入元素”的最大异或值,
// 这样天然保证两个下标不同。
static int solve_xor(int n, int hi) {
    trie_cnt = 0;
    trie[0].child[0] = 0;
    trie[0].child[1] = 0;
    int best = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i];
        int u = 0;
        int res = 0;
        for (int b = hi; b >= 0; b--) {
            int want = ((x >> b) & 1) ^ 1;   // 这一位想走相反分支,异或结果才能置 1
            int nxt = trie[u].child[want];
            if (nxt) {
                res |= (1 << b);
                u = nxt;
            } else {
                u = trie[u].child[want ^ 1];
            }
        }
        if (res > best) best = res;

        u = 0;
        for (int b = hi; b >= 0; b--) {
            int bit = (x >> b) & 1;
            int nxt = trie[u].child[bit];
            if (!nxt) {
                nxt = new_node();
                trie[u].child[bit] = nxt;
            }
            u = nxt;
        }
    }
    return best;
}

// c=3 或运算:逐位贪心 + 超集判定。
// 记 t_i = cand & ~a[i](cand 中 a[i] 缺的位),则“存在一对数的 OR 包含 cand”
// 等价于“存在下标 i,使 t_i 被另一个元素包含”。
// 先对值域做一次高维后缀和得到 sup:sup[m] = 是否存在元素包含 m。
// 查询时 sup[t] != 0 就说明有某个元素包含 t;由于 a[i] 与 t 的位完全不相交,
// t != 0 时这个元素一定不是 a[i] 自己;t == 0 时 sup[0] 恒为 1,
// 对应“a[i] 自己已覆盖 cand,任取另一个下标即可”(题面保证 n >= 2)。
static int solve_or(int n, int hi) {
    int dom = 1 << (hi + 1);
    memset(sup, 0, (size_t)dom);
    for (int i = 0; i < n; i++) sup[a[i]] = 1;
    for (int b = 0; b <= hi; b++) {
        int bit = 1 << b;
        for (int m = 0; m < dom; m++) {
            if ((m & bit) == 0 && sup[m | bit]) sup[m] = 1;
        }
    }
    int cur = 0;
    for (int b = hi; b >= 0; b--) {
        int cand = cur | (1 << b);
        for (int i = 0; i < n; i++) {
            if (sup[cand & ~a[i]]) {   // cand 中 a[i] 缺的位有别的元素兜住
                cur = cand;
                break;
            }
        }
    }
    return cur;
}

int main(void) {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T-- > 0) {
        int n, c;
        if (scanf("%d %d", &n, &c) != 2) break;
        int mx = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if (a[i] > mx) mx = a[i];
        }
        int hi = hi_bit(mx);   // 值域最高位,答案不会超过它

        int ans;
        if (c == 1) ans = solve_and(n, hi);
        else if (c == 2) ans = solve_xor(n, hi);
        else ans = solve_or(n, hi);
        printf("%d\n", ans);
    }
    return 0;
}

Python 同算法短解法。异或一档改用"前缀集合"写法:第 bb 轮只取每个数的高 B−bB - b 位前缀, 若存在两个前缀 pp 与 p⊕candp \oplus \text{cand} 同时出现,说明这一位可以要。 或用 int 承载 2202^{20} 位的超集标记,做 SOS 时整块位并行。

python
#!/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-08 02:12
# update_at: 2026-10-08 02:12

import sys

AND, XOR, OR = 1, 2, 3  # 题面的算子编号:1=与, 2=异或, 3=或(顺序与直觉不同)

type Values = list[int]  # 一组数据的序列,元素是 20 位以内的位掩码


def bit_class_mask(step: int, dom: int) -> int:
    """dom 位掩码:下标中第 step 位为 1 的那些位置全置 1(step 是 2^b,不是 b)。

    长度为 2*step 的一小段里,高半段(下标 ∈ [step, 2*step))全是 1;把这段模式
    按周期翻倍原样拼下去即可,避免用大数除法构造周期性掩码。
    """
    pattern = ((1 << step) - 1) << step  # 一个周期 2*step 里的高半段
    width = step << 1
    while width < dom:
        pattern |= pattern << width  # 把已有模式原样再拼一份,周期翻倍
        width <<= 1
    return pattern & ((1 << dom) - 1)


def superset_flags(values: Values, dom: int) -> bytes:
    """返回 sup,第 m 位为 1 表示存在某个值 v 满足 m ⊆ v(v 补齐 m 缺的位)。

    高维后缀和(SOS)逐位做 F |= (F & 第 b 位为 1 的下标) >> 2^b:把“含第 b 位”
    的下标标记下放到“不含第 b 位”的下标。整张 dom 位的标记表由一个 Python 大整数
    承载,一轮只需数次大整数位运算,位并行的代价远低于逐下标循环。
    """
    bytes_len = (dom + 7) >> 3
    bits = bytearray(bytes_len)
    for v in values:
        bits[v >> 3] |= 1 << (v & 7)
    flags = int.from_bytes(bits, 'little')

    for b in range(dom.bit_length() - 1):  # dom 是 2 的幂,位数就是 bit_length()-1
        step = 1 << b
        flags |= (flags & bit_class_mask(step, dom)) >> step
    return flags.to_bytes(bytes_len, 'little')


def max_and(values: Values, hi: int) -> int:
    """与运算(c=1):高位到低位贪心,每轮只留下包含候选掩码的元素。

    "至少两个元素都包含 cand" 对 cand 单调(cand 变小只会更易成立),所以从高位
    贪心得到的掩码就是最大的两数 AND;含 cand 者必然含上一轮的 cur,只需在 kept 里筛。
    """
    kept, cur = values, 0
    for b in range(hi, -1, -1):
        cand = cur | 1 << b
        nxt = [v for v in kept if (v & cand) == cand]  # 含 cand 者必然含 cur,可只筛 kept
        if len(nxt) >= 2:  # 这一位要得起:至少有 2 个元素盖住 cand
            kept, cur = nxt, cand
    return cur


def max_xor(values: Values, hi: int) -> int:
    """异或运算(c=2):按前缀集合贪心,看候选答案能否由两个数的高位前缀拼出。

    第 b 轮保留每个数的高 (hi-b+1) 位前缀;若存在两个前缀 p、p^cand 同时出现,
    说明有一对元素在这段高位上的异或恰为 cand,这一位可以要。前缀集合的求交/判交
    都在 C 层完成,避免逐个前缀做 Python 循环。
    """
    best, mask = 0, 0
    for b in range(hi, -1, -1):
        mask |= 1 << b
        prefixes = {v & mask for v in values}
        cand = best | 1 << b
        # 存在两个前缀互为 cand 的异或,说明有一对元素拼得出 cand
        pairable = not prefixes.isdisjoint(p ^ cand for p in prefixes)
        if pairable:
            best = cand
    return best


def max_or(values: Values, hi: int) -> int:
    """或运算(c=3):先做值域超集标记 sup,再逐位贪心。

    记 cand 为目标答案掩码、t = cand & ~v 是元素 v 缺的位。存在一对元素的 OR 包含
    cand,等价于存在某个 v 使"有元素包含 t"——t 与 v 的位不相交,所以那个元素不是 v
    自己;t 为 0 时 v 自己已覆盖 cand,题面 n>=2 保证还有别的下标可以配对。
    """
    dom = 1 << (hi + 1)
    sup = superset_flags(values, dom)
    gaps = [~v for v in values]  # ~v 是补集,cand & ~v 取 cand 中 v 缺的位

    cur = 0
    for b in range(hi, -1, -1):
        cand = cur | 1 << b
        # 缺位集合先去重(同一个缺位只需查一次),再逐位读 sup 表
        missing = {cand & g for g in gaps}
        covered = any(sup[m >> 3] >> (m & 7) & 1 for m in missing)
        if covered:
            cur = cand
    return cur


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n, c = next(data), next(data)
        values = [next(data) for _ in range(n)]
        hi = max(values).bit_length() - 1  # 值域最高位,答案不会超过它

        if c == AND:
            out.append(str(max_and(values, hi)))
        elif c == XOR:
            out.append(str(max_xor(values, hi)))
        else:
            out.append(str(max_or(values, hi)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

设 B=20B = 20 为值域位数,V=2BV = 2^B 为值域大小。

情形 时间 空间
c=1c = 1 与 O(Bn)O(Bn) O(n)O(n)
c=2c = 2 异或 O(Bn)O(Bn) O(Bn)O(Bn)(Trie 节点)
c=3c = 3 或 O(B⋅2B+Bn)O(B \cdot 2^B + Bn) O(2B)O(2^B)

代入 n=105n = 10^5:与和异或约 2×1062 \times 10^6 次位运算,或约 2×1072 \times 10^7 次(SOS 主导), T=6T = 6 组全顶格也只有约 1.3×1081.3 \times 10^8,在 1500 ms 下余量充足。内存方面 Trie 节点数组约 2×106×82 \times 10^6 \times 8 B =16= 16 MB,超集表 2202^{20} 字节 =1= 1 MB, 都远低于 128 MB。

Python 侧最重的部分是或运算的 SOS:本解把 2202^{20} 位标记表压进一个 int 做位并行, 每轮量级相当于一次 2202^{20} 位的与、右移、或,再配合 any 逐元素查表。 实测本机(CPython 3.14.7 / Apple M4 Pro):最坏输入(T=6T = 6、每组 n=105n = 10^5、c=3c = 3) 整体 0.55 s,单组约 0.09 s;c=2c = 2 的六组顶格数据 0.35 s。运行时间充裕, 预期不会触发 1500 ms 时限,但 CPython 在不同评测机上的常数波动较大, 保守起见仍应知悉本解依赖大整数位运算这一非平凡常数因子。

总结

本题的骨架是"按位独立 + 单调性贪心",三个算子各配一件值域工具:

  • 与:判定谓词"至少两个元素包含 cand\text{cand}",直接扫序列数个数即可,O(Bn)O(Bn);
  • 异或:0-1 Trie,边查边插保证下标不同,O(Bn)O(Bn);
  • 或:tit_i 与 AiA_i 位不相交这一观察把"配对"化归为"查某个掩码是否被元素包含", 用 SOS 高维后缀和一次预处理、O(Bn)O(Bn) 判定。

三个情形的共同点是:都把"(n2)\binom{n}{2} 个数对"替换成了"BB 个二进制位上的独立决策"。 这正是 Ai<220A_i < 2^{20} 这一条件(位数少、值域可用数组铺开)给出的自由度—— 若无此条件,c=1,3c = 1, 3 的这两个判定就没有了可以铺开的值域表。

最后提醒两个实现坑:一是题面 cc 与算子的对应顺序(22 是异或、33 是或)容易记反; 二是"或的最大值取最大两个数"是错解,反例 {10,5,12}\{10, 5, 12\} 中 10or⁡5=1510 \operatorname{or} 5 = 15 才是答案。

关于本题数据

本目录的测试数据由素材源自带的 data.py 分层生成(转写为本题解时未改动), 题面亦为网络重建版本,与 OJ 原站的官方数据、出题意图可能存在差异。 data.py 的期望值由“手推断言 + 结构断言”而非独立暴力程序核对, 因此本页的正确性依据以 runner 实测结果与区间/结构断言为准; 另外用 O(n2)O(n^2) 暴力程序对素材源 std.cpp 做了 300 组固定种子随机对拍(含重复值、 极端值域、全同值等构造),std.cpp 与暴力完全一致,可以认为本题的素材源实现可靠。