思路
首先读题:题目要求使得操作后的数组的字典序最大，换而言之，每次操作后的数字一定要最大（根据字典序的定义可知），那么这相当于是一个“贪心”，因为答案的每次操作必定是当前状态的最优解。那么我们可以把重新排列 $ a $ 数组看做改变添加 $ a_i $ 的顺序，使得每次当前的 $ b_i = a_i~\mathsf{OR}b_{i-1} $ 最大。
题目中让我们用"按位或"进行操作，那么咱就想到把每一个 $ a_i $ 二进制化！如 $ 7 = (111)_2 $ 和 $ 11 = (1011)_2 $，然后我们就可以操作起来了。在添加第一个数的时候，每个数对答案的贡献都等于它本身（任意一个数对 $ 0 $ 按位或都等于它们自己），那么第一次一定是添加最大的数。那么第二次每个数的贡献是多少呢？
因为对答案的贡献是以“按位或”计算的，所以在位上“重复”的贡献是无效的。比如 $ (1011)_2 $ 已经添加进了答案，第一位( $ 2^0 $ )和第二位( $ 2^1 $ )都已经被占有了，此时再加入$ (111)_2 $，它的第一、二位（和为 $ 3 $）就无法产生贡献，但是因为第三位（ $ 2^2 $ ）还没有被占用，他依然可以带来贡献 $ 2^2 = 4 $ 的贡献。
所以，我们可以在每次添加答案后，计算当前答案添加进去对后续答案贡献的影响。添加 $ a_x $ 的影响对于每一个 $ a_i $ 是 $ a_i~\mathsf{AND}a_x $，这意味着，在 $ a_i $ 和 $ a_x $ 相同的位上，再添加 $ a_i $ 已经无法添加贡献了。最后，如上文所说，我们就每次贪心地枚举每一个 $ a_i $，每次选取能造成贡献最大的那一个。另外不用担心重复选取的情况，因为它 $ a_x $ 的贡献已经减去 $ a_x~\mathsf{OR}a_x $ 了，是不会有任何贡献的。
等等...在 $ n = 2 \times 10^5 $ 和 $ a_i = 10^9$ 的范围内它不会TLE吗？的确不会。因为我们是按位操作的，对于统计的答案 $ b_i $ 来说，$ 10^9 $ 最多只有 $ 2^{30} $ 的 $ 30 $ 位（ $ 2^{30} = 1073741824 $ ），所以顶多进行 $ 30 $ 次操作就可以手动跳出循环（因为此时每个数的贡献都为 $ 0 $ ）。剩下的数字无法造成任何贡献，我们直接顺序（或者按照您喜欢的方式）输出即可。（感谢指出错误：循环的上界与 $ n $ 无关，而是与 $ a_i $ 的最大值有关）
另外，在证明循环最多只持续 $ 30 $ 次后，直接按照题意以贪心的思路打模拟也是可以过的，在这里不多做讨论了。
代码
#include<bits/stdc++.h>
using namespace std;
int t,n;
struct lb{
int v,orgv;
bool used;
}l[200006];
int main(){
std::ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n;
for(int i = 1;i <= n;i++){
cin>>l[i].v;
l[i].orgv = l[i].v;
l[i].used = 0;//多组输入记得清空used
}
for(int i = 1;i <= n;i++){
int maxv = 0,maxpos = 0;
for(int pos = 1;pos <= n;pos++){
if(l[pos].v > maxv){
maxv = l[pos].v;
maxpos = pos;
}
}
for(int pos = 1;pos <= n;pos++){
l[pos].v -= (l[pos].v & maxv);
}
if(maxv == 0){
break;
}
l[maxpos].used = 1;
cout<<l[maxpos].orgv<<" ";
}
for(int i = 1;i <= n;i++){
if(l[i].used == 0){
cout<<l[i].orgv<<" ";
}
}
cout<<endl;
}
return 0;
}
Comments NOTHING