A34572. 烹饪问题问题描述有 N 种食材，编号从 0 至 N-1，其中第 种食材的美味度为 ai。不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为x和y，那么它们的契合度为 x and y。其中， and运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足0，再逐位进行与运算。例如，12与6的二进制表示分别为 1100 和 0110 ，将它们逐位进行与运算，得到 …
填空题
困难
知识点
题目描述
烹饪问题
问题描述
有 N 种食材，编号从 0 至 N-1，其中第 种食材的美味度为 ai。
不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为x和y，那么它们的契合度为 x and y。其中， and运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足0，再逐位进行与运算。例如，12与6的二进制表示分别为 1100 和 0110 ，将它们逐位进行与运算，得到 0100 ，转换为十进制得到4，因此12 and 6 =4。在 C++ 或 Python 中，可以直接使用 & 运算符表示与运算。
现在，请你找到契合度最高的两种食材，并输出它们的契合度。
输入描述
第一行一个整数 N，表示食材的种数。
接下来一行N个用空格隔开的整数，依次为 a0,...... an-1，表示各种食材的美味度。
输出描述
输出一行一个整数，表示最高的契合度。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入1
3
1 2 3样例输出1
2样例解释1
可以编号为1,2的食材之间的契合度为 2 and 3 =2，是所有食材两两之间最高的契合度。
样例输入2
5
5 6 2 10 13样例输出2
8样例解释2
可以编号为3,4的食材之间的契合度为 10 and 13 =8，是所有食材两两之间最高的契合度。
数据规模
对于40%的测试点，保证 N ≤1000；
对于所有测试点，保证 N ≤1000000 ，0 ≤ai≤2147483647。
参考答案
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAX_N = int(1e6) + 100;
int a[MAX_N];
int sort(int l,int r,int k) {
while(l <= r) {
while ((l <= r) && (a[l] >> k & 1)) l++;
while ((l <= r) && (!(a[r] >> k & 1))) r--;
if (l <= r) swap(a[l++], a[r--]);
}
return r;
}
int main() {
int n, j, ans=0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 31; i >= 0; i--)
if ((j = sort(1, n, i)) >= 2) {
ans = ans | 1 << i;
n = j;
}
printf("%d\n", ans);
return 0;
}
上一题
下一题