Codeforces Round #648 (Div. 2) E、Maximum Subsequence Value

题意：
从a数组中选取一个长度为k的子序列，使得该子序列的value值最大。一个子序列的value值为2^i的和，i为二进制形式下的有效位。当且仅当该子序列中不少于k-2个数的二进制在该位下为1时，该位有效。

思路：
对于选取小于等于3个数，那么这些数每个数的位数都对答案有贡献。
当随着k增大，要满足的条件就是k-2个数的相同位置二进制数要相同，所以随着k越大，答案就越小。
对于k大于3时，当某位有效时，说明至少有k-2个数的该位为1，这种情况显然更加难以满足。但是若从这个子序列中挑三个数，则根据鸽巢原理必然有一个数该位有效。所以最优的是选择个数为 3，然后暴力枚举。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 2e5+10;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair<int,int>
#define pal pair<ll,ll>
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);++i)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);--i)
#define endl '\n'
#define ll long long
const ll mod = 1e9+7;
ll a[man];

signed main() {
	#ifndef ONLINE_JUDGE
		//freopen("in.txt", "r", stdin);
		//freopen("out.txt","w",stdout);
	#endif
	int n;
	scanf("%d",&n);
	ll res = 0;
	for(int i = 1;i <= n;i++){
		scanf("%lld",&a[i]);
		res = max(res,a[i]);
	}
	for(int i = 1;i <= n;i++){
		for(int j =1;j <= n;j++){
			for(int k = 1;k <= n;k++){
				res = max(res,a[i]|a[j]|a[k]);
			}
		}
	}
	cout <<res << endl;
	return 0;
}

本文地址：https://blog.csdn.net/weixin_43571920/article/details/107214071