题目链接:codeforces1365E
题目大意:
给定一个序列,定义其非空子序列(大小为 k k k)的价值是每个元素的二进制数中第 i ( i > = 0 ) i(i>=0) i(i>=0) 位上 1 1 1 的个数如果大于 m a x ( 1 , k − 2 ) max(1, k-2) max(1,k−2),则 ans += 2^i
,求最大的价值。
题目思路:
显然,当 k ≤ 3 k \le 3 k≤3 时全选。
当 k > 3 k>3 k>3 时,每个位上需要的 1 1 1 也会增加。假设我们已经选了 3 3 3 个数,当选第 4 4 4 个的时候,我们可以把他加进来,但这会使得后面需要的 1 1 1 增加;既然第 4 4 4 个数可以加进来,说明它可以替换掉三个数中的某一个,所以每次枚举 3 3 3 个数的或和即可。
参考代码:
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 510;
int n;
ll a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
ans = max(ans, a[i] | a[j] | a[k]);
}
}
}
cout << ans << endl;
return 0;
}