自动搬运

查看原文

来自洛谷，原作者为

	little_Cabbage AFOed.luogu

搬运于2025-08-24 21:16:00，当前版本为作者最后更新于2024-01-28 17:45:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

博客食用体验更佳

这是一道暴力水题。

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

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

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

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

• $k=2$ 时，显然 $1$ 位二进制时前 $2$ 个能取到最优。

• $k=n$ 时可以，则 $k=n+1$ 时，如果所有数的最高位都相同则所有数的最高位无关。

• 由归纳假设，$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 记录