【Code Forces 320D】【贪心+暴力】 Or Game 数列乘k次x后求最大or值

本文主要是介绍【Code Forces 320D】【贪心+暴力】 Or Game 数列乘k次x后求最大or值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【传送门】
http://codeforces.com/contest/579/problem/D

【题意】
这题其实很水，然而HDU-ACM集训队的南神熊神都挂掉了咩哈哈

给你n个数，我们一共可以做k次操作，每次任意选择一个数，并把数值*x
你来决定操作，使得操作之后，所有数的or值尽可能大

【类型】
贪心+暴力

【分析】
这题首先有一个非常暴力的贪心，
就是把最大的数乘k遍x，然后再求总or值。
这样可以创造出前所未有的高位，会产生更大的or值。

但是这个是错误的。
比如
我们有3个数
15 13 8
15=8+4+2+1
13=8+4+1
可以乘1次3
我们如果对15*3，得到的数是45=32+8+4+1，总or值为32+8+4+1=45
如果对13*3，得到的数是39=32+4+2+1，总or值为32+8+4+2+1=47

所以我们是并非对最大的数贪心的。
同时，只对位数最高的数做贪心也是错的，
如数据
3 1 3
16 13 13
16=16
13=8+4+1
如果16*3得到48=32+16，总or值为32+16+8+4+1
如果13*3得到39=32=4+2+1，总or值为32+16+8+4+2+1，更大。

【时间复杂度&&优化】
因为or不满足减法关系，所以我一开始是用二进制拆分的方式，O(nlogn)求对某个x暴力*x后的总or值。
然而更优秀的方式是，积累前缀和和后缀和~
这题还有一个优化，就是把k次*x先预处理了

【trick】
在不tle的情况下，越暴力好写的算法是越有意义的！

【数据】
Input
3 1 2
1 1 1
Output
3

Input
4 2 3
1 2 4 8
Output
79

【代码】

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#include<algorithm>
#include<time.h>
#include<bitset>
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
using namespace std;
const int N=2e5+10,M=0,Z=1e9+7,maxint=2147483647,ms31=522133279,ms63=1061109567,ms127=2139062143;const double eps=1e-8,PI=acos(-1.0);//.0
map<int,int>mop;
struct A{};
int n,k,x;
int a[N];
int b[N],c[N];
int main()
{while(~scanf("%d%d%d",&n,&k,&x)){LL y=1;while(k--)y*=x;for(int i=1;i<=n;i++)scanf("%d",&a[i]);b[0]=0;for(int i=1;i<=n;i++)b[i]=b[i-1]|a[i];c[n+1]=0;for(int i=n;i>=1;i--)c[i]=c[i+1]|a[i];LL ans=0;for(int i=1;i<=n;i++){gmax(ans,b[i-1]|c[i+1]|a[i]*y);}printf("%I64d\n",ans);}return 0;
}