Or Game

wjh15101051's space

卧薪尝胆，厚积薄发。

Or Game

Date: Thu Jul 19 17:00:19 CST 2018

In Category: NoCategory

Description：

现在有 $n$ 个数 $a_1,a_2,a_3,\cdots,a_n$ 。你最多可以进行 $k$ 次操作，每次操作你可以将其中一个数乘以 $x$ 。找出使得 $a_1|a_2|...|a_n$ 最大的方法。

$1\le n\le200000$ $1\le k\le10$ $2\le x\le8$

Solution：

$x\ge 2$ ，说明一次操作最高位一定会向上移动，那么最优解一定是把所有操作都加在一个数上面，于是枚举这个数前缀后缀和求一下取最大就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,k,x;

#define MAXN 200010

ll a[MAXN];

ll presum[MAXN],sufsum[MAXN];

int main()

{

	cin >> n >> k >> x;

	for(int i = 1;i <= n;++i)cin >> a[i];

	for(int i = 1;i <= n;++i)presum[i] = presum[i - 1] | a[i];

	for(int i = n;i >= 1;--i)sufsum[i] = sufsum[i + 1] | a[i];

	ll power = 1;

	for(int i = 1;i <= k;++i)power = power * x;

	ll ans = 0;

	for(int i = 1;i <= n;++i)ans = max(ans,presum[i - 1] | (a[i] * power) | sufsum[i + 1]);

	cout << ans << endl;

	return 0;

}

In tag: 算法-贪心

wjh15101051