【位运算 暴力】CF1742G Orray
一扶苏一
·
·
题解
CF1742G Orray
Description
给定一个数列 a，要求对 a 重排，使得重排后 a 的前缀或和数组 b 字典序最大。
这里前缀或和的定义是：b_i = a_1 \operatorname{or} a_2 \operatorname{or} \dots \operatorname{or} a_i，其中 \operatorname{or} 表示二进制按位异或操作。
### Analysis
首先考虑暴力怎么做：
为了保证字典序最大，$b_1$ 一定是 $a$ 中最大的数，然后依次确定 $b_2, b_3, \dots b_n$。想要确定 $b_i$，只需要枚举还没有选择的 $a_j$，使得 $b_i = b_{i - 1} \operatorname{or} a_j$ 最大 即可。
考虑一个显然的结论：一定存在一个 $j$，使得 $b_1 < b_2 < b_3 < \dots < b_j = b_{j + 1} = b_{j + 2} = \dots = b_n$。这就是说，$b$ 数列的前半部分一定互不相同，后半部分一定相同，证明留做习题。
考虑如果 $b_i > b_{i - 1}$，那么 $b_i$ 的二进制一定比 $b_{i - 1}$ 多至少一个 $1$（因为 $b_i$ 是由 $b_{i - 1}$ 或另一个数得到，$b_{i - 1}$ 在二进制下 $1$ 的位置在 $b_i$ 中一定也是 $1$）。而 $b_i$ 二进制只有 $\lceil\log_2 a\rceil = 30$ 位，所以 $b_i > b_{i - 1}$ 的位置最多只有 $30$ 个，结合上一段中的结论，这样的位置只会出现在 $b$ 的前 $30$ 位。
所以只需要通过第一段中的暴力方法确定 $b$ 中前三十位的位置，剩余位置均与 $b_{30}$ 相同。
考虑运算量：每组数据会进行 $\min(n, 30)$ 次枚举，每次枚举 $O(n)$，最坏情况下枚举了 $30 \Sigma n$ 次 $a_j$，可以接受。
### Code
```cpp
#include <vector>
#include <iostream>
#include <algorithm>
typedef long long int ll;
const int maxn = 200005;
int a[maxn];
bool op[maxn];
std::vector<int> Ans;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T, n;
for (std::cin >> T; T; --T) {
Ans.clear();
std::cin >> n;
for (int i = 1; i <= n; ++i) op[i] = false;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
int ans = 0;
for (int i = 1, lim = std::min(n, 30); i <= lim; ++i) {
int tans = ans, pos = 0;
for (int i = 1; i <= n; ++i) if (op[i] == false) {
if ((ans | a[i]) >= tans) {
pos = i; tans = ans | a[i];
}
}
ans = tans;
op[pos] = true;
Ans.push_back(pos);
}
for (int i = 1; i <= n; ++i) if (op[i] == false) Ans.push_back(i);
for (auto &&u : Ans) {
std::cout << a[u] << ' ';
}
std::cout << '\n';
}
}
```