G5004 [GESP202312 五级] 烹饪问题 题解

知识点：位运算、贪心、按位构造。

解题思路

从最高位到最低位尝试把答案当前位设1，统计有多少输入数包含候选mask的全部1位；至少两数满足就保留这一位。

为什么正确

高位权值超过全部低位之和，优先保留可行高位最优；两数同时包含mask正是按位与包含mask的充要条件。

易错点

必须用(x&mask)==mask，不能仅检查当前一位；要求选两种食材，计数至少为2。

复杂度

时间O(n log A)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    int ans=0;
    for(int b=30;b>=0;b--) {
        int mask=ans|(1<<b),c=0;
        for(int x:a)if((x&mask)==mask)c++;
        if(c>=2)ans=mask;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。