一、题目解读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;
- }
五、总结本解法巧妙利用位运算特性，将“寻找**AND值”转化为逐位决策问题，通过动态构建位掩码实现高效筛选。相比暴力枚举所有元素组合，该算法通过“提前终止无效位检查”和“计数满足条件元素”两大优化，大幅降低时间复杂度。这一思路对处理位操作相关的优化问题具有重要参考价值，尤其在编程竞赛中可显著提升解题效率。
| 
发表于 2025-7-21 10:53:08
