gesp(C++五级)（6）洛谷：B3930：[GESP202312 五级] 烹饪问题

gesp(C++五级)（6）洛谷：B3930：[GESP202312 五级] 烹饪问题

题目描述

有 N N N 种食材，编号从 0 0 0 至 N − 1 N-1 N−1，其中第 i i i 种食材的美味度为 a i a_i ai​。

不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为 x x x 和 y y y ，那么它们的契合度为 $x\ \text{and}\ y $。

其中， and \text{and} and 运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足 ，再逐位进行与运算。例如， 12 12 12 与 6 6 6 的二进制表示分别为 1100 1100 1100 和 0110 0110 0110 ，将它们逐位进行与运算，得到 0100 0100 0100 ，转换为十进制得到 4，因此 12 and 6 = 4 12 \text{and} 6 = 4 12and6=4。在 C++ 或 Python 中，可以直接使用 & 运算符表示与运算。

现在，请你找到契合度最高的两种食材，并输出它们的契合度。

输入格式

第一行一个整数 N N N，表示食材的种数。

接下来一行 N N N 个用空格隔开的整数，依次为 a 1 , ⋯   , a N a_1,\cdots,a_N a1​,⋯,aN​，表示各种食材的美味度。

输出格式

输出一行一个整数，表示最高的契合度。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

2

样例 #2

样例输入 #2

5
5 6 2 10 13

样例输出 #2

8

提示

样例解释 1

可以编号为 1 , 2 1,2 1,2 的食材之间的契合度为 2  and  3 = 2 2\ \text{and} \ 3=2 2 and 3=2，是所有食材两两之间最高的契合度。

样例解释 2

可以编号为 3 , 4 3,4 3,4 的食材之间的契合度为 10  and  13 = 8 10\ \text{and}\ 13=8 10 and 13=8，是所有食材两两之间最高的契合度。

数据范围

对于 40 % 40\% 40% 的测试点，保证 N ≤ 1 , 000 N \le 1,000 N≤1,000；

对于所有测试点，保证 N ≤ 1 0 6 N \le 10^6 N≤106， 0 ≤ a i ≤ 2 , 147 , 483 , 647 0\le a_i \le 2,147,483,647 0≤ai​≤2,147,483,647。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
/*优化思路：
  k位二进制时，前k+1位一定能渠道最优（感兴趣的可以证明下）
  本题的数据最多31位二进制，所以找前32位大的数据枚举即可 
  1、先对原数组排序（从大到小排序） 
  2、取前32个最大数，依次枚举做&运算，取最大值就是答案 
  备注：优化后的双重循环的复杂度最多32*32，sort排序的复杂度为n*logn，不会TLE 
*/ 
const int N=1e6+10;
int n,a[N],ans=0;
bool cmp(int x,int y){
	return x>y;
} 
int main(){ 
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	//数组排序，降序排序 
	sort(a+1,a+n+1,cmp);
	//n有可能不够32个
	int m=min(n,32);//m是需要做&运算的数的个数 
	//枚举 
	for(int i=1;i<=m-1;i++){//枚举：&前面的x 
		for(int j=i+1;j<=m;j++){//枚举：&后面的y
			ans=max(ans,a[i]&a[j]); 
		} 
	}
	//输出答案
	cout<<ans; 
	return 0;
} 

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容