GESP 题解库 / 5 级题解 / [GESP202312 五级] 烹饪问题 · 第 15 / 23 题
GESP202312 五级 · B3930 · 中等

烹饪问题

求任意两种食材美味度按位与的最大值。

📊
N ≤ 10⁶
食材种类
🔢
aᵢ ≤ 2³¹−1
数值范围
⚡
O(31N)
时间复杂度
🎯
按位贪心 + 子集计数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有 N 种食材,第 i 种的美味度为 aᵢ。两种食材的"契合度"定义为 x AND y(按位与)。求任意两种食材契合度的最大值。

💡
人话翻译:暴力枚举两两组合是 O(N²) = 10¹²,必然超时。正确思路是"从高位到低位贪心构造答案":依次尝试让答案的第 30、29、…、0 位为 1,能凑出来就保留。判断"能否凑出"的方法是:数一数有多少个数包含目标掩码的所有位,≥ 2 就说明可行。

🔍 关键词提取

按位与按位贪心子集计数位运算

已知条件

项目说明
输入第一行 N;第二行 N 个整数 aᵢ
输出最高的契合度
数据范围N ≤ 10⁶
数值范围0 ≤ aᵢ ≤ 2147483647 = 2³¹ − 1
目标max(aᵢ AND aⱼ)(i ≠ j)

需要解决的问题

02
思维导图
整理解题思路的全貌
🍳 从高位按位构造答案
🧠 贪心依据
2³⁰ > 2²⁹ + … + 2⁰
高位权重压倒低位
所以优先保住高位
逐位尝试即可
🔍 判定方法
试让第 b 位为 1
mask = ans | (1<
统计含 mask 全部位的数的个数
≥ 2 则第 b 位可取 1
⚙️ 实现
ans = 0
b 从 30 递减到 0
每轮 O(N) 扫描
总 O(31N) ≈ 3 × 10⁷
⚠️ 易错点
枚举两两组合(N² 超时)
位上限写 30 而不是 31
只数 1 个数(需要 ≥ 2)
用 int 处理 2³¹−1 边界
03
样例手算推导
两个样例的逐位推演

🧮 样例 1:a = [1, 2, 3],答案 2

1 = 01₂、2 = 10₂、3 = 11₂。最高位只到第 1 位,我们从第 30 位开始试(高位都凑不出)。

试探位mask = ans | 2^b含 mask 全部位的数个数决策
30 ~ 2…无0跳过,ans 不变
110₂ = 22(10₂)、3(11₂)2✅ ans = 2
011₂ = 33(11₂)1❌ 不够 2 个
1
第 1 位试探

mask = 2(二进制 10)

检查每个数:1 AND 2 = 0 ≠ 2 ✗

2 AND 2 = 2 == 2 ✓

3 AND 2 = 2 == 2 ✓

共 2 个数 → 够 2 个(可以选 2 和 3)

✅ ans = 2

2
第 0 位试探

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)

🧮 样例 2:a = [5, 6, 2, 10, 13],答案 8

先看二进制表示。

数二进制(4 位)说明
50101
60110
20010
101010含第 3 位
131101含第 3 位
1
第 3 位(值 8)

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

2
第 2 位(值 4)不能要

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

3
第 1 位、第 0 位

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)

🔑
注意样例 2 的关键:第 2 位虽然 13 有、10 没有,但要求的是"两个数都包含 mask 的所有位"——10 缺第 2 位,所以不能和第 2 位一起取。这就是"子集计数"的含义:mask 必须完整地包含在某个数里。
04
解法对比
按位贪心 vs 暴力枚举

⚔️ 解法对比

🟢 按位贪心 + 子集计数(推荐) 推荐

从第 30 位往下,逐位尝试置 1,统计能否凑出两个数

  • 时间 O(31N)
  • N = 10⁶ 时约 3 × 10⁷
  • 代码 15 行
  • 空间 O(N)
💡
可行性条件:至少要有两个不同的数,它们都完整包含 mask 的所有 1 位——这样它们的按位与才至少包含 mask。用"计数 ≥ 2"来判定。

🟠 枚举两两组合

双重循环求所有 aᵢ AND aⱼ 的最大值

  • 时间 O(N²) = 5 × 10¹¹
  • 必然超时
  • 代码最短(4 行)
  • 只适用于 N ≤ 1000
⚠️
注意题目数据:N ≤ 10⁶ 而只有 40% 的测试点 N ≤ 1000,所以暴力只能拿部分分。这也提示我们:看到 N 很大但数位只有 31 位,就该往"按位处理"想。

📈 性能对比

方案运算量(N = 10⁶)可行性
按位贪心约 3 × 10⁷✅ 稳过
两两枚举约 5 × 10¹¹❌ 超时
05
算法流程图
从高位逐位尝试构造答案
开始读入 N 和数组 a;ans = 0b 从 30 递减到 0mask = ans | (1 << b);cnt = 0扫描所有 aᵢ:若 (aᵢ & mask) == mask 则 cnt 加 1cnt 是否 ≥ 2?是 ✓ans = mask(保留这一位)否 ✗弃掉这一位输出 ans结束b 减 1 继续试低位
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🍳 最高契合度构造器

输入一组美味度,程序会逐位构造最大契合度并展示每次试探。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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;决策要两个不同的数才能形成一对
⚠️
四个坑:① 用 O(N²) 暴力(10⁶ 规模必然超时);② 位循环写成 b < 31 从 31 开始(aᵢ ≤ 2³¹−1,最高位是 30);③ 判定写成 cnt >= 1(需要两个不同的数);④ 移位 1 << 30 时用 int 是安全的,但写 1 << 31 会溢出。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 2 3
2题面样例 1:2 AND 3 = 2
5
5 6 2 10 13
8题面样例 2:10 AND 13 = 8
2
0 0
0两个 0,契合度为 0
2
2147483647 2147483647
2147483647两个最大值,按位与等于自身
4
7 7 7 7
7多个相同的数,取任意两个
✅
自查清单:① 按位贪心了吗?② 位从 30 开始吗?③ 判定用了 ≥ 2 吗?

🚨 易错点清单

⚠️
暴力枚举:N = 10⁶ 时两两组合约 5 × 10¹¹,会超时。
⚠️
位循环范围错:aᵢ ≤ 2³¹−1,最高位是第 30 位(2³⁰ = 1073741824)。
⚠️
判定条件写成 cnt ≥ 1:需要两个不同的数才能形成一对,所以是 cnt ≥ 2。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(31N)
空间复杂度
O(N)
N 最大
10⁶
运算量
约 3 × 10⁷

时间怎么算的?

空间都用在哪?

需要存下 N 个整数。

✅ 约 3000 万次位运算,C++ 一秒内完成。相比 O(N²) 的 5 × 10¹¹,优化了四个数量级。

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 > 低位之和所有"按位贪心"的正确性依据
🌟
思考题:如果题目改成求"最大按位或(OR)",还需要这套贪心吗?(提示:不需要——因为 x OR y 的最大值就是"把所有数的所有 1 位都合起来",直接把所有 aᵢ 按位或一遍即可,O(N) 搞定。正是"AND 要求两个数都要有这一位"这个约束,才让本题需要贪心 + 计数。)