CF1365E 题解

$\text{Description}$

给出一个长度为 $n$ 的数列 $\{a\}$，你需要选出一个子序列，使其价值最大，输出最大的价值。

对于一个长度为 $k$ 的子序列，若在这个子序列中有不少于 $\max(1,k-2)$ 个数的二进制位 $i$ 上是 $1$，则其价值增加 $2^i$。

$n\le 500$

$\text{Solution}$

这个数据范围容易引人遐想。

首先我们分析 $k$ 最好为多少。我们发现在一定程度上，添加一个数进入候选子序列一定是不优的。

结合数据范围，我们猜测最优的子序列长度不超过 $3$，然后写一下发现就过了。

证明？人类智慧还需要证明？

$\text{Code}$

#include<bits/stdc++.h>
#define REG register
using namespace std;

typedef long long ll;

inline void read(ll& x){
	static char c;
	while(!isdigit(c=getchar()));x=c^48;
	while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

ll n;

ll A[505];

ll Ans;

int main(){
	read(n);
	for(REG int i=1;i<=n;++i) read(A[i]);
	if(n==1){printf("%lld\n",A[1]);return 0;}
	if(n==2){printf("%lld\n",A[1]|A[2]);return 0;}
	for(REG int i=1;i<=n;++i)
    	for(REG int j=i+1;j<=n;++j)
        	for(REG int k=j+1;k<=n;++k)
            	Ans=max(Ans,A[i]|A[j]|A[k]);
	printf("%lld\n",Ans);
}

2021-03-20

CF Chapter2 简要题解

CodeForces

CF1365E 题解

CF1365E 题解

$\text{Description}$

$\text{Solution}$

$\text{Code}$

Catalogue

Links

Categories

Tag Cloud

Recent

Archives

Tags

Recent

Archives

Tags

Your browser is out-of-date!