求任意两种食材美味度按位与的最大值。
有 N 种食材,第 i 种的美味度为 aᵢ。两种食材的"契合度"定义为 x AND y(按位与)。求任意两种食材契合度的最大值。
按位与按位贪心子集计数位运算
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;第二行 N 个整数 aᵢ |
| 输出 | 最高的契合度 |
| 数据范围 | N ≤ 10⁶ |
| 数值范围 | 0 ≤ aᵢ ≤ 2147483647 = 2³¹ − 1 |
| 目标 | max(aᵢ AND aⱼ)(i ≠ j) |
mask = ans | (1 << b),统计满足 (aᵢ AND mask) == mask 的个数,≥ 2 就可行1 = 01₂、2 = 10₂、3 = 11₂。最高位只到第 1 位,我们从第 30 位开始试(高位都凑不出)。
| 试探位 | mask = ans | 2^b | 含 mask 全部位的数 | 个数 | 决策 |
|---|---|---|---|---|
| 30 ~ 2 | … | 无 | 0 | 跳过,ans 不变 |
| 1 | 10₂ = 2 | 2(10₂)、3(11₂) | 2 | ✅ ans = 2 |
| 0 | 11₂ = 3 | 3(11₂) | 1 | ❌ 不够 2 个 |
mask = 2(二进制 10)
检查每个数:1 AND 2 = 0 ≠ 2 ✗
2 AND 2 = 2 == 2 ✓
3 AND 2 = 2 == 2 ✓
共 2 个数 → 够 2 个(可以选 2 和 3)
✅ ans = 2
mask = 2 | 1 = 3(二进制 11)
检查:1 AND 3 = 1 ≠ 3 ✗
2 AND 3 = 2 ≠ 3 ✗
3 AND 3 = 3 == 3 ✓
只有 1 个数 → 不够,第 0 位不能要
❌ ans 保持 2
答案 2 ✓(2 AND 3 = 2)
先看二进制表示。
| 数 | 二进制(4 位) | 说明 |
|---|---|---|
| 5 | 0101 | |
| 6 | 0110 | |
| 2 | 0010 | |
| 10 | 1010 | 含第 3 位 |
| 13 | 1101 | 含第 3 位 |
mask = 8(二进制 1000)
5 AND 8 = 0 ✗
6 AND 8 = 0 ✗
2 AND 8 = 0 ✗
10 AND 8 = 8 ✓
13 AND 8 = 8 ✓
共 2 个 → 可行
✅ ans = 8
mask = 8 | 4 = 12(二进制 1100)
10 AND 12 = 8 ≠ 12 ✗(10 = 1010,缺第 2 位)
13 AND 12 = 12 == 12 ✓(13 = 1101)
5、6、2 也不满足
只有 1 个 → 不够 2 个
❌ ans 保持 8
mask = 8 | 2 = 10:10 ✓、13 AND 10 = 8 ✗ → 仅 1 个
mask = 8 | 1 = 9:10 AND 9 = 8 ✗、13 AND 9 = 9 ✓ → 仅 1 个
都不满足
❌ ans 最终为 8
答案 8 ✓(10 AND 13 = 1010 ∧ 1101 = 1000 = 8)
从第 30 位往下,逐位尝试置 1,统计能否凑出两个数
双重循环求所有 aᵢ AND aⱼ 的最大值
| 方案 | 运算量(N = 10⁶) | 可行性 |
|---|---|---|
| 按位贪心 | 约 3 × 10⁷ | ✅ 稳过 |
| 两两枚举 | 约 5 × 10¹¹ | ❌ 超时 |
输入一组美味度,程序会逐位构造最大契合度并展示每次试探。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int a[1000005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int ans = 0; // 从最高位(第 30 位)往低位贪心 for (int b = 30; b >= 0; b--) { int mask = ans | (1 << b); // 统计有多少个数"完整包含" mask 的所有 1 位 int cnt = 0; for (int i = 0; i < n; i++) { if ((a[i] & mask) == mask) cnt++; } if (cnt >= 2) ans = mask; // 至少两个,可行 } printf("%d\n", ans); return 0; }
(a[i] & mask) == mask 是什么意思?它表示"mask 里所有的 1,a[i] 在对应位置也都是 1",也就是 mask 是 a[i] 的位掩码子集。这等价于 (a[i] | mask) == a[i] 或 (a[i] & ~mask) == 0,但写成 (a[i] & mask) == mask 最直观好记。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
b 从 30 到 0 | 位遍历 | aᵢ ≤ 2³¹−1,最高位是第 30 位 |
mask = ans | (1 << b) | 试探掩码 | 在已确定的高位基础上,试加当前位 |
(a[i] & mask) == mask | 子集判定 | 判断 aᵢ 是否完整包含 mask 的所有位 |
if (cnt >= 2) ans = mask; | 决策 | 要两个不同的数才能形成一对 |
b < 31 从 31 开始(aᵢ ≤ 2³¹−1,最高位是 30);③ 判定写成 cnt >= 1(需要两个不同的数);④ 移位 1 << 30 时用 int 是安全的,但写 1 << 31 会溢出。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 2 | 题面样例 1:2 AND 3 = 2 |
5 | 8 | 题面样例 2:10 AND 13 = 8 |
2 | 0 | 两个 0,契合度为 0 |
2 | 2147483647 | 两个最大值,按位与等于自身 |
4 | 7 | 多个相同的数,取任意两个 |
需要存下 N 个整数。
✅ 约 3000 万次位运算,C++ 一秒内完成。相比 O(N²) 的 5 × 10¹¹,优化了四个数量级。
// 按位贪心构造"最大 AND"的模板 int ans = 0; for (int b = 30; b >= 0; b--) { int mask = ans | (1 << b); int cnt = 0; for (int i = 0; i < n; i++) if ((a[i] & mask) == mask) cnt++; if (cnt >= 2) ans = mask; } // 常见的"子集判定"三种等价写法 bool has = ((a[i] & mask) == mask); // 最直观 bool has2 = ((a[i] | mask) == a[i]); // 等价 bool has3 = ((a[i] & ~mask) == 0); // 等价 // 位运算的小技巧 // x & (x - 1) 消掉最右边的 1 // x & (-x) 取出最低位的 1 // __builtin_popcount(x) 数 1 的个数 // 关键:看到"N 很大、但数值位宽很小(≤ 31 位)",优先想"按位处理"
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 按位贪心 | 高位优先,逐位构造 | 最大 AND / 最大 XOR / 最大 OR 类问题 |
| 子集判定 | (x & mask) == mask | 位掩码的子集关系判断 |
| 高位权重优势 | 2^k > 低位之和 | 所有"按位贪心"的正确性依据 |
x OR y 的最大值就是"把所有数的所有 1 位都合起来",直接把所有 aᵢ 按位或一遍即可,O(N) 搞定。正是"AND 要求两个数都要有这一位"这个约束,才让本题需要贪心 + 计数。)