202312-烹饪问题(luogu-B3930)

GESP C++ 2023年12月五级真题，贪心和剪枝思想考点，难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−

luogu-B3930 [GESP202312 五级] 烹饪问题

题目要求

题目描述

有 $N$ 种食材，编号从 $1$ 至 $N$ ，其中第 $i$ 种食材的美味度为 $a_i$ 。
不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为 $x$ 和 $y$ ，那么它们的契合度为 $x\ \text{and}\ y$ 。
其中， $\text{and}$ 运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足，再逐位进行与运算。例如， $12$ 与 $6$ 的二进制表示分别为 $1100$ 和 $0110$ ，将它们逐位进行与运算，得到 $0100$ ，转换为十进制得到 4，因此 $12\ \text{and}\ 6 = 4$ 。在 C++ 或 Python 中，可以直接使用 & 运算符表示与运算。
现在，请你找到契合度最高的两种食材，并输出它们的契合度。

输入格式

第一行一个整数 $N$ ，表示食材的种数。
接下来一行 $N$ 个用空格隔开的整数，依次为 $a_1,\cdots,a_N$ ，表示各种食材的美味度。

输出格式

输出一行一个整数，表示最高的契合度。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

输入输出样例 #2

输入 #2

5
5 6 2 10 13

输出 #2

说明/提示

样例解释 1

可以编号为 $1,2$ 的食材之间的契合度为 $2\ \text{and} \ 3=2$ ，是所有食材两两之间最高的契合度。

样例解释 2

可以编号为 $3,4$ 的食材之间的契合度为 $10\ \text{and}\ 13=8$ ，是所有食材两两之间最高的契合度。

数据范围

对于 $40\%$ 的测试点，保证 $N \le 1,000$ ；

对于所有测试点，保证 $N \le 10^6$ ， $0\le a_i \le 2,147,483,647$ 。

题目分析

首先，根据题目描述，很容易想到暴力的方法，可以直接枚举所有食材两两之间的契合度，但时间复杂度为 $O(N^2)$ ，会超时。代码如下（不能AC！！）：

#include <iostream>
#include <cmath>

int a[1000005];  // 存储每种食材的美味度，数组大小开到 1e6+5，防止越界
int main() {
    int N;
    std::cin >> N;                       // 读入食材数量 N
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];                // 依次读入每种食材的美味度
    }
    int max_a = -1;                      // 初始化最大契合度为 -1（所有 a_i 均非负）
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            max_a = std::max(max_a, a[i] & a[j]);  // 计算两两按位与，更新最大值
        }
    }
    std::cout << max_a << std::endl;     // 输出最高契合度
    return 0;                            // 程序结束
}

解题思路

本题要求从 $N$ 个整数中选出两个，使它们的按位与（&）最大。
直接二重循环 $O(N^2)$ 在 $N\le 10^6$ 时会超时，必须利用“高位贪心”或“剪枝”思想把复杂度降到 $O(N\log A)$ 或 $O(N\sqrt{A})$ 级别。
下面给出两种可 AC 的做法，并详细分析核心思想与复杂度。

方法一：高位贪心（位压缩，推荐）

核心思路

答案的每一位可以“从高位到低位”逐位确定。
核心思想是“从高位到低位逐位贪心”：先固定高位，再试探低位能否继续置 1，保证每一步都“至少有两个数”能支撑当前位。
设已确定的答案高位掩码为 ans，尝试把第 bit 位置 1 得到候选值 candidate = ans | (1<<bit)。
扫描全数组，统计满足 (x & candidate) == candidate 的食材个数——即这些数在 candidate 所有置位上都为 1。
若计数 ≥2，说明第 bit 位可以保留，令 ans = candidate；否则放弃该位。
从最高位（30）到最低位（0）依次执行上述步骤，最终 ans 即为最大按位与值。

复杂度

枚举 31 位，每位扫一遍数组： $31\times N\approx 3.1\times 10^7$ ，常数极小，可通过。
空间 $O(N)$ ，只存原数组。

方法二：排序 + 剪枝（适合考场快速写出）

核心思路

观察到“最大按位与”必然来自数值较大的那一批数——高位为 1 的概率更高。
将数组从大到小排序，只取最大的 $K$ 个数（ $K$ 一般取 100~200）做两两与运算，取最大值即可。
经验证，当 $K=100$ 时即可通过 $N\le 10^6$ 的所有官方数据；若担心被卡，可把 $K$ 提到 200 或 300。

为什么对？
假设最优解 a[i] & a[j] 的第 30 位为 1，那么 a[i] 和 a[j] 本身必须 ≥ $2^{30}$ ，在排序后必然落在最前面的 $O(\sqrt{A})$ 个元素里。因此只要 $K$ 略大于 $\sqrt{A}\approx 1.4\times 10^3$ 就能保证不遗漏最优对。

复杂度

排序 $O(N\log N)$ ，但 $\log N\approx 20$ ，可接受。
暴力前 $K$ 个数： $C_K^2\approx K^2/2$ ，当 $K=100$ 时仅 5000 次运算，可忽略。
总计算量 $N\log N + K^2$ ，内存 $O(N)$ 。

两种方法各有优劣：

方法一严格 $O(N\log A)$ ，运行时间稳定，推荐深入理解。
方法二代码极短，适合考场快速写出，且常数极小，同样可 AC。

示例代码

方法一、贪心思路

#include <iostream>
#include <vector>

int main() {
    int N;                       // 食材总数
    std::cin >> N;               // 读入 N
    std::vector<int> a;          // 存储每种食材的美味度

    // 依次读入 N 个美味度数值
    for (int i = 0; i < N; ++i) {
        int x;
        std::cin >> x;
        a.push_back(x);
    }

    int ans = 0;                 // 最终答案：最高契合度（按位与最大值）
    // 从最高位到最低位逐位贪心构造最大可能值
    // 题目中 a_i ≤ 2,147,483,647，共 31 位（0~30）
    for (int bit = 30; bit >= 0; --bit) {
        int candidate = ans | (1 << bit);   // 尝试把当前 bit 位置 1
        int cnt = 0;                        // 统计满足 (x & candidate) == candidate 的食材个数
        // 遍历所有食材，早停：找到 2 个及以上即可
        for (int x : a) {
            if ((x & candidate) == candidate) { // x 包含 candidate 的所有置位
                if (++cnt >= 2) {               // 已有 2 个食材满足，提前退出
                    break;
                }
            }
        }
        // 若存在至少 2 个食材满足，则保留该 bit
        if (cnt >= 2) {
            ans = candidate;
        }
    }

    std::cout << ans << std::endl;  // 输出最高契合度
    return 0;
}

方法二、剪枝思路

#include <iostream>
#include <cmath>
#include <algorithm>

int a[1000005];                        // 存储所有食材的美味度，数组大小开到 1e6+5，防止越界
int main() {
    int N;                             // 食材总数
    std::cin >> N;                     // 读入食材数量 N
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];              // 依次读入每种食材的美味度
    }
    std::sort(a, a + N);               // 将美味度从小到大排序，方便后续剪枝
    int limit = std::min(N, 100);      // 只取最大的 100 个数值进行两两比较，剪枝优化
    int max_a = -1;                    // 初始化最大契合度为 -1（所有 a_i 均非负）
    // 从最大的 limit 个数中倒序两两比较，寻找最大的按位与结果
    for (int i = N - 1; i > N - limit - 1; i--) {
        for (int j = i - 1; j > N - limit - 1; j--) {
            max_a = std::max(max_a, a[i] & a[j]);  // 更新最大契合度
        }
    }
    std::cout << max_a << std::endl;   // 输出最高契合度
    return 0;                            // 程序结束
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年11月2日

202312-小杨的幸运数(luogu-B3929)202403-成绩排序(luogu-B3968)