S2OJ - 1036. 打打牌

#题面

#题目描述

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

机房里，有 $n$ 个同学在打牌，小胡同学和小王同学正在观战。经过若干轮的较量之后，每个人都有了个积分，第 $i$ 个人的积分为 $a_i$ ，把所有的人的积分全部按位或起来即为整个牌局的总积分（也就是 $a_1 | a_2 | ... | a_n$）。

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

#输入

第一行两个正整数 $n$ 和 $x$ 接下来一行有 $n$ 个正整数，代表 $a_1, a_2, ..., a_n$ 。

#输出

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

#样例输入

3 2
1 1 1

#样例输出

3

#数据规模与约定

• 对于 $50\%$ 的数据，$n \leq 2000$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 100000, 2 \leq x \leq 8, 0 \leq a_i \leq 10^9$ 。

#思路

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

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#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;
}