Div. 4 Codeforces Round #827 A-G( 二 ) _生活百科

用 \(val\) 记录目前哪个位置还缺 \(1\)。每次枚举没有取过的数字，找到一个数 \(a[pos]\) 使 a[pos] & val 最大，表示有效位组成最大的数字。然后取出来，并通过 val &= ~a[pos] 把 \(val\) 中对应的 \(1\) 删除（把 \(a[pos]\) 取反，原来的 \(1\) 现在都为 \(0\)，然后与 \(val\) 就能删掉 \(val\) 对应的 \(1\)）。最后把 \(a[pos]\) 交换到末尾的有效数字，实现逻辑删除。
因为 int 有 \(31\) 位，每次删除删的是结果最大的，最多删除 \(31\) 次就能达到这个序列或的最大值。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[200007];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];int val = ~(1 << 31);for (int i = 1;i <= min(31, n);i++) {int pos = 1;for (int j = 1;j <= n - i + 1;j++) {if ((val & a[j]) > (val & a[pos])) pos = j;}cout << a[pos] << ' ';val &= ~a[pos];swap(a[n - i + 1], a[pos]);}for (int i = 1;i <= n - min(31, n);i++) cout << a[i] << ' ';cout << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}

Div. 4 Codeforces Round #827 A-G( 二 )

推荐阅读

汽车贴膜前需要洗车吗汽车贴膜前要洗车吗?

瘦麒麟臂方法瘦胳膊最有效的方法

糖不甩怎么做才Q

形容经历了事情的成语是什么

白煮牛肉的家常做法大全白煮牛肉的家常做法

梦见下牙掉了,但没流血是什么意思

金鱼眼面相解析，有金鱼眼的人运势怎么样

关于本玉12号简述本玉12号

双子座的床上功夫

2022年护士年终工作总结 2022美工个人年终工作总结

手机无响应的解决方法应该怎么解决呢

宝马有什么技术

诗歌鉴赏蜀相咏史怀古诗蜀相的作者

猫咪渴了的表现

母亲节要买什么礼物,分享几款走心的

越狱第3季中第几集越狱成功？

抗皱六胜肽精华液的使用方法六胜肽抗皱精华液使用方法

开元通宝680万图片 &#8211; 开元通宝2020价格

怎么去胶？

蓝牙耳机使用小技巧蓝牙耳机的正确使用方法