GESP2023年五级题烹饪问题：从暴力枚举到位运算优化深度解...
https://dajuwangluo.cn/zb_users/upload/2025/06/202506061749182940215106.jpg一、题目分析我们需要在N种食材中找到两种食材，使得它们美味度的按位与运算结果最大。直接暴力枚举所有组合的时间复杂度是O(N²)，对于大数据量会超时。我们需要更高效的算法。二、高效解法思路我们可以从最高位开始，尝试构建最大的按位与结果。对于每一位，我们检查是否有至少两个数字在该位为1，并且这些数字在前面的高位也满足我们的构建要求。1. 算法思路
[*]从最高位(第30位)开始逐位检查
[*]尝试构建最大的按位与结果
[*]对于每一位，检查是否有至少两个数字满足当前构建的模式
[*]如果有，保留这一位；否则，跳过这一位
2. 关键点
[*]使用mask来跟踪当前构建的模式
[*]使用temp来尝试设置当前位
[*]统计满足条件的数字数量
3. 复杂度分析
[*]时间复杂度：O(32*N) ≈ O(N)，非常高效
[*]空间复杂度：O(1)，只使用了常数个额外变量
4. 优化点
[*]提前终止：一旦找到两个满足条件的数字就可以停止统计
[*]位运算优化：使用位运算代替乘除法
三、完整代码
#include <iostream>
#include <vector>
using namespACe std;
int findMaxAnd(vector<int>& nums) {
int mask = 0;
int max_and = 0;
// 从最高位开始检查
for (int i = 30; i >= 0; i--) {
// 尝试设置这一位
mask |= (1 << i);
int count = 0;
int temp = max_and | (1 << i);
// 统计有多少数字包含当前构建的模式
for (int num : nums) {
if ((num & mask) == temp) {
count++;
if (count >= 2) break;
}
}
// 如果有至少两个数字满足，保留这一位
if (count >= 2) {
max_and = temp;
} else {
mask ^= (1 << i); // 撤销这一位
}
}
return max_and;
}
int main() {
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a;
}
cout << findMaxAnd(a) << endl;
return 0;
}
来源：GESP2023年五级题烹饪问题：从暴力枚举到位运算优化深度解析
页:
[1]