Skip to content

S2OJ - 1036. 打打牌

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

小胡同学是个热爱打牌的好孩子。

机房里,有 nn 个同学在打牌,小胡同学和小王同学正在观战。经过若干轮的较量之后,每个人都有了个积分,第 ii 个人的积分为 aia_i ,把所有的人的积分全部按位或起来即为整个牌局的总积分(也就是 a1a2...ana_1 | a_2 | ... | a_n)。

聪明的小胡同学很快就算出了总分数,小王同学眼看小胡同学比自己算得快,非常不爽,决定刁难一下小胡同学。众所周知,小王同学有个幸运数字 xx。小王让小胡从 nn 个人随意挑选出一个人,将他的积分乘上 xx,之后再计算牌局的总积分。小王同学问小胡同学牌局最大可能的总积分是多少,这可难倒了小胡同学,你能帮帮他吗?

输入

第一行两个正整数 nnxx 接下来一行有 nn 个正整数,代表 a1,a2,...,ana_1, a_2, ..., a_n

输出

输出一个整数,代表最大可能的总积分。

样例输入

3 2
1 1 1

样例输出

3

数据规模与约定

  • 对于 50%50\% 的数据,n2000n \leq 2000
  • 对于 100%100\% 的数据,1n100000,2x8,0ai1091 \leq n \leq 100000, 2 \leq x \leq 8, 0 \leq a_i \leq 10^9

思路

先预处理出来前缀或数组和后缀或数组,在计算答案时只需比较 prei1(ai×x)sufi+1{pre}_{i-1} | (a_i \times x) | suf_{i+1}ansans 的大小即可。

代码

#include <bits/stdc++.h>

using namespace std;

int n;
long long x, a[1000005], pre[1000005], suf[1000005], ans;

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] | a[i];
    }
    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] | a[i];
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, pre[i - 1] | (a[i] * x) | suf[i + 1]);
    }
    cout << ans << endl;
    return 0;
}