【21.37%】【codeforces 579D】"Or" Game

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given n numbers a1, a2, …, an. You can perform at most k operations. For each operation you can multiply one of the numbers by x. We want to make as large as possible, where denotes the bitwise OR.

Find the maximum possible value of after performing at most k operations optimally.

Input
The first line contains three integers n, k and x (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8).

The second line contains n integers a1, a2, …, an (0 ≤ ai ≤ 109).

Output
Output the maximum value of a bitwise OR of sequence elements after performing operations.

Examples
input
3 1 2
1 1 1
output
3
input
4 2 3
1 2 4 8
output
79
Note
For the first sample, any possible choice of doing one operation will result the same three numbers 1, 1, 2 so the result is .

For the second sample if we multiply 8 by 3 two times we’ll get 72. In this case the numbers will become 1, 2, 4, 72 so the OR value will be 79 and is the largest possible result.

【题目链接】:http://codeforces.com/contest/579/problem/D

【题解】

显然，二进制位1最靠左的那个数字乘上数字会让最靠左的数字再靠左一点;
这样做是最优的策略；
但是
如果有多个数字二进制1最靠左,即最靠左的1相同;则不能随便选；
比如
1 0 0 0
1 0 1 1
1 1 0 1
这3个数字;
假设要乘的数字x是2；只能乘1次;
这三个数字依次是
8
11
13
如果把2乘最大的那个数字13
0 1 0 0 0
0 1 0 1 1
1 1 0 1 0
最后取or运算
结果为1 1 0 1 1
如果把2乘8
1 0 0 0 0
0 1 0 1 1
0 1 1 0 1
则再取or运算
结果为
1 1 1 1 1
显然后者更大；
所以不能单纯地就认为乘那个最大的数字就好了；
但如果最靠左的1的位置不是所有数字中最靠左的；那就不可能去乘它了；
所以乘了一次之后；肯定是继续去乘刚才乘的数字;
比如刚才的乘2之后变成了
1 0 0 0 0
0 1 0 1 1
0 1 1 0 1
显然继续让那个10000乘2是更优的;因为最高位移动一下幅度更大;
枚举要乘哪个数字、然后一直乘就可以了；
处理出前缀or和后缀or;预处理出x^k;x为要乘的数字;k为允许乘的次数

【完整代码】

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 20e4+100;

int n,k,x;
LL a[MAXN],qz[MAXN],hz[MAXN];

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    cin >> n >> k >> x;
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    for (int i = 1;i <= n;i++)
        qz[i] = qz[i-1] | a[i];
    for (int i = n;i >= 1;i--)
        hz[i] = hz[i+1] | a[i];
    LL temp = x;
    for (int i = 1;i <= k-1;i++)
        temp*=x;
    LL ans = 0;
    for (int i = 1;i <= n;i++)
    {
        LL temp1 = a[i]*temp;
        ans = max(ans,qz[i-1] | temp1 | hz[i+1]);
    }
    cout << ans << endl;
    return 0;
}