欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-04-19 14:08:36
题意:从a数组中选取一个长度为k的子序列,使得该子序列的value值最大。一个子序列的value值为2^i的和,i为二进制形式下的有效位。当且仅当该子序列中不少于k-2个数的二进制在该位下为1时,该位有效。思路:对于选取小于等于3个数,那么这些数每个数的位数都对答案有贡献。当随着k增大,要满足的条件就是k-2个数的相同位置二进制数要相同,所以随着k越大,答案就越小。对于k大于3时,当某位有效时,说明至少有k-2个数的该位为1,这种情况显然更加难以满足。但是若从这个子序列中挑三个数,则根据鸽巢原理必...

题意:
从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