【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;
}
最新文章
- 蓝灯(lantern)在服务器(vps)上运行
- Ubuntu下输入su - [root]后提示“su:认证失败”
- 第五周技术博客发表 web 网页开发
- 从零开始完整Electron桌面开发(1)搭建开发环境
- iOS中常用技术链接
- jad批量反编译class和jadeclipse集成到eclipse的设置方法
- js加载优化
- JavaScript学习笔记:数组reduce()和reduceRight()方法
- 使用zzip和minizip解压缩文件
- Linux中添加管理员权限问题:xxx is not in the sudoers file. This incident will be reported.
- Bourn Again Shell编程
- Linux服务器tomcat无法通过ip加端口访问
- spring配置问题
- 纯js异步无刷新请求(只支持IE)【原】
- 查看CPU/CACHE的拓扑结构
- Hdu1151 Air Raid(最小覆盖路径)
- 【BZOJ2631】tree
- 规范命名CSS
- Illegal instruction错误的定位---忽略编译期警告的代价
- 用emoji表情包来可视化北京市历史天气状况!