CF1365 E.Maximum Subsequence Value【位运算】

题目链接：codeforces1365E

题意

给定一个序列，定义其非空子序列（大小为 ）的价值是每个元素的二进制数中第 位上 的个数如果大于 ，则 ans += 2^i，求最大的价值。

题解

显然，当 时全选。

当 时，每个位上需要的 也会增加。假设我们已经选了 个数，当选第 个的时候，我们可以把他加进来，但这会使得后面需要的 增加；既然第 个数可以加进来，说明它可以替换掉三个数中的某一个，所以每次枚举 个数的或和即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}