GESP2023年五级题烹饪问题：从暴力枚举到位运算优化深度解...

15303105423

一、题目分析

我们需要在N种食材中找到两种食材，使得它们美味度的按位与运算结果最大。直接暴力枚举所有组合的时间复杂度是O(N²)，对于大数据量会超时。我们需要更高效的算法。

二、高效解法思路

我们可以从最高位开始，尝试构建最大的按位与结果。对于每一位，我们检查是否有至少两个数字在该位为1，并且这些数字在前面的高位也满足我们的构建要求。

1. 算法思路

• 从最高位(第30位)开始逐位检查
• 尝试构建最大的按位与结果
• 对于每一位，检查是否有至少两个数字满足当前构建的模式
• 如果有，保留这一位；否则，跳过这一位
  
  

2. 关键点

• 使用mask来跟踪当前构建的模式
• 使用temp来尝试设置当前位
• 统计满足条件的数字数量
  
  

3. 复杂度分析

• 时间复杂度：O(32*N) ≈ O(N)，非常高效
• 空间复杂度：O(1)，只使用了常数个额外变量
  
  

4. 优化点

• 提前终止：一旦找到两个满足条件的数字就可以停止统计
• 位运算优化：使用位运算代替乘除法
  
  

三、完整代码

1. #include <iostream>
   
2. #include <vector>
   
3. using namespACe std;
   
4. 
   
5. int findMaxAnd(vector<int>& nums) {
   
6.     int mask = 0;
   
7.     int max_and = 0;
   
8.    
   
9.     // 从最高位开始检查
   
10.     for (int i = 30; i >= 0; i--) {
    
11.         // 尝试设置这一位
    
12.         mask |= (1 << i);
    
13.         int count = 0;
    
14.         int temp = max_and | (1 << i);
    
15.         
    
16.         // 统计有多少数字包含当前构建的模式
    
17.         for (int num : nums) {
    
18.             if ((num & mask) == temp) {
    
19.                 count++;
    
20.                 if (count >= 2) break;
    
21.             }
    
22.         }
    
23.         
    
24.         // 如果有至少两个数字满足，保留这一位
    
25.         if (count >= 2) {
    
26.             max_and = temp;
    
27.         } else {
    
28.             mask ^= (1 << i); // 撤销这一位
    
29.         }
    
30.     }
    
31.    
    
32.     return max_and;
    
33. }
    
34. 
    
35. int main() {
    
36.     int N;
    
37.     cin >> N;
    
38.     vector<int> a(N);
    
39.     for (int i = 0; i < N; i++) {
    
40.         cin >> a[i];
    
41.     }
    
42.    
    
43.     cout << findMaxAnd(a) << endl;
    
44.     return 0;
    
45. }

复制代码

来源：GESP2023年五级题烹饪问题：从暴力枚举到位运算优化深度解析