【GESP】C++五级真题（贪心和剪枝思想） luogu-B3930 [GESP202312 五级] 烹饪问题
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
1
2
3
1 2 3
输出 #1
1
2
输入输出样例 #2
输入 #2
1
2
5
5 6 2 10 13
输出 #2
1
8
说明/提示
样例解释 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！！）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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。
示例代码
方法一、贪心思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}
方法二、剪枝思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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; // 程序结束
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
