按算子分治:与用逐位贪心加超集计数,异或用 0-1 Trie 求最大异或对,或用值域超集变换加逐位贪心,三者都是 O(20n) 级。
OJ: roj
题目 ID: 1776
难度:提高+/省选-
标签:位运算字典树动态规划贪心python
创建: 2026-10-08 02:12
更新: 2026-10-08 02:12
形式化题目
给定长度为
多组数据:第一行 n c 与
需要注意算子的编号顺序与直觉不同:
朴素做法枚举
正解
思路
情形 :按位与
按位与"同为 1 才为 1",所以答案掩码的每一位都要求至少两个数在该位上同时为 1。
更一般地,对任意候选掩码
存在
使 至少两个下标满足 (即 )。
必要性显然;充分性同样显然:取这两个元素配对,它们的 AND 含
这条性质对
可行性判定就是数一数有多少个
单组共
情形 :按位异或
异或"相异为 1",是和"前缀相同/相异"绑定最深的一种运算,标准做法是 0-1 Trie(二进制字典树):
把数按二进制从高位到低位插入,形成一棵深度
要让
单组复杂度
情形 :按位或
或运算的单调性方向与与运算一致(或的结果只增不减),所以仍可逐位贪心:
存在
使 存在某个下标 ,使 中 缺的那些位能被另一个元素补齐。
记
与 的位完全不相交( 只取 为 0 的位),所以 时, 包含 的那个元素一定不是 自己,自匹配天然被排除; 时 自己就覆盖了整个 ,任取另一个下标即可,题面保证 。
于是只需要一张"是否存在元素包含掩码
一遍之后
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 位"]
一个必须避开的错解。 容易想当然地认为"或的最大值一定由最大值和次大值配对得到",
这是错的。反例
代码
C++ 逐算子实现(与运算逐位贪心、异或走 0-1 Trie、或用 SOS + 贪心):
/**
* 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 同算法短解法。异或一档改用"前缀集合"写法:第 int 承载
#!/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()复杂度
设
| 情形 | 时间 | 空间 |
|---|---|---|
代入
Python 侧最重的部分是或运算的 SOS:本解把 int 做位并行,
每轮量级相当于一次 any 逐元素查表。
实测本机(CPython 3.14.7 / Apple M4 Pro):最坏输入(
总结
本题的骨架是"按位独立 + 单调性贪心",三个算子各配一件值域工具:
- 与:判定谓词"至少两个元素包含
",直接扫序列数个数即可, ; - 异或:0-1 Trie,边查边插保证下标不同,
; - 或:
与 位不相交这一观察把"配对"化归为"查某个掩码是否被元素包含", 用 SOS 高维后缀和一次预处理、 判定。
三个情形的共同点是:都把"
最后提醒两个实现坑:一是题面
关于本题数据
本目录的测试数据由素材源自带的 data.py 分层生成(转写为本题解时未改动),
题面亦为网络重建版本,与 OJ 原站的官方数据、出题意图可能存在差异。
data.py 的期望值由“手推断言 + 结构断言”而非独立暴力程序核对,
因此本页的正确性依据以 runner 实测结果与区间/结构断言为准;
另外用 std.cpp 做了 300 组固定种子随机对拍(含重复值、
极端值域、全同值等构造),std.cpp 与暴力完全一致,可以认为本题的素材源实现可靠。