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
上一篇: 快速成为抖音内容运营高手的心法
下一篇: 2135 价钱统计 Python3
推荐阅读
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree(dfs)
-
Codeforces Round #670 (Div. 2) E. Deleting Numbers(交互,素数构造)
-
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
-
Codeforces Round #648 (Div. 2) E、Maximum Subsequence Value
-
Codeforces Round #566 (Div. 2) E(矩阵快速幂)
-
Educational Codeforces Round 98 (Rated for Div. 2) A-E 题解
-
Codeforces Round #670 (Div. 2) (A~E题解)
-
Codeforces Round #485 (Div. 2) - E - Petr and Permutations