1. 首頁 > 生活百科 > >

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

推薦閱讀