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

_little_Cabbage_ · 2024-01-28 17:45:26 · 题解

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

博客食用体验更佳

这是一道暴力水题。

我们可以双重循环枚举每一种情况，但是这样会超时。

其实我们只需要枚举前 32 大的数的情况就行了，证明如下（引用的 Bingxiu 的证明，非常感谢）：

• int 范围内的非负整数就是 31 位二进制。

• 数学归纳法，下证 k-1 位二进制时前 k 个一定能取到最优 (k\ge2)。

• 由归纳假设，k-2 位二进制前 k-1 个数必有最优，所以加上第一位就有前 k-1 个数必有最优。

• 如果有至少两个最高位为 1，至少一个最高位为 0，则舍弃所有最高位为 0 的数，归入第一类情况，则前 k-1 个必有最优。

• 如果仅有一个最高位为 1，其它都为 0，则舍弃最高位为 1 的数，归入第一类情况，则去掉最大数（最高位为 1 的数）后前 k-1 个必有最优，故前 k 个必有最优。

时间复杂度 O(\min(n,32)^2)。

AC 代码

#include<bits/stdc++.h>
using namespace std;
long long a[1000010];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+n+1,cmp);
    n=min(n,32);
    long long mx=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            {
                mx=max(mx,a[i]&a[j]);
            }
        }
    }
    cout<<mx;
    return 0;
}

AC 记录