当前位置：首页 > GESP > 2023年GESP五级烹饪问题解题指南：位运算优化AND最大值求解

2023年GESP五级烹饪问题解题指南：位运算优化AND最大值求解

3个月前 (07-17)

一、题目解读

2023年GESP五级编程竞赛中的“烹饪问题”（对应洛谷B3930）要求从给定的整数数组中寻找一个元素，使其与数组中其他任意元素的按位与（AND）结果最大。题目需在保证结果尽可能大的同时，确保该元素本身存在于原数组中。这一问题的关键在于高效遍历与筛选符合条件的元素，避免暴力枚举带来的超时风险。

二、解题思路

采用位运算优化策略，核心思想是从高位到低位逐位构建目标元素，而非直接遍历数组元素。通过预设位掩码（mask）和临时结果（temp），每次尝试将当前位（从第30位开始）加入目标元素，并统计数组中满足“与操作后等于temp”的数值个数。若存在至少两个元素符合，则保留该位；否则撤销，确保最终结果既满足条件又是最大可能的AND值。

三、解题步骤

1. 初始化：设置位掩码mask=0，初始最大值max_and=0，从最高位（第30位）开始检查。

2. 逐位尝试：

将当前位i加入mask（mask |= (1 << i)）。

构建临时目标值temp（max_and | (1 << i)）。

遍历数组，统计满足(num & mask) == temp的元素个数count。

若count≥2，则保留该位（更新max_and = temp）；否则撤销该位（mask ^= (1 << i)）。

3. 返回结果：最终max_and即为符合条件且最大的AND值。

四、代码与注释

#include <iostream>
#include <vector>
using namespace std;

// 寻找数组中元素的最大AND值
int findMaxAnd(vector<int>& nums) {
    int mask = 0;          // 位掩码，用于构建目标值
    int max_and = 0;       // 当前最大AND值

    // 从最高位开始检查（30位对应int类型最大二进制位）
    for (int i = 30; i >= 0; i--) {
        // 尝试设置这一位
        mask |= (1 << i);          // 将第i位设为1
        int count = 0;
        int temp = max_and | (1 << i); // 临时目标值（当前位加入max_and）

        // 统计有多少数字包含当前构建的模式
        for (int num : nums) {
            if ((num & mask) == temp) { // 若num与mask的与结果等于temp
                count++;
                if (count >= 2) break; // 若找到≥2个，无需继续遍历
            }
        }

        // 如果有至少两个数字满足，保留这一位
        if (count >= 2) {
            max_and = temp;
        } else {
            mask ^= (1 << i); // 撤销这一位（异或操作清除第i位）
        }
    }

    return max_and;
}

int main() {
    int N;
    cin >> N;          // 输入数组长度
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];    // 读入数组元素
    }

    cout << findMaxAnd(a) << endl; // 输出结果
    return 0;
}