题目描述
https://codeforces.com/problemset/problem/925/C
Solution
首先不妨设现在的前缀异或和为 $s$，要添加的数为 $k$，那么 $s~xor~k>s$ 的充要条件是 $k$ 的最高位在 $s$ 中为 $0$
首先给出一个贪心策略，我们从小到大枚举这次要填的数的最高位能填则，每个最高位只需要枚举任意一个
然后我们来思考一下这个东西为什么是对的
首先我们不妨假设现在一个找到了一个满足条件的排列，然后还剩下一些 $1$ 没有放
我们现在令奇数的个数为 $y$，$1$ 的个数为 $x$
当 $x\le y+1$，我们一定能找到一个合适的放的方案，实际上就是两个 $1$ 之间隔了奇数个奇数
那么我们现在不止考虑 $1$，我们来考虑一个最高位是 $k$ 的数，我们把它看成 $1$，那么现在对于它来说的 $y$ 就是那些大于等于 $2^{k+1}$ 的数
注意到这些 $1$ 之间的顺序是无所谓的，所以我们只需要贪心的先放最高位较小的数就行了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <stack>
#include <vector>
#define maxn 100010
#define ll long long
using namespace std;
int n;
ll a[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; stack<ll> S[60];
for (int i = 1; i <= n; ++i) {
ll x; cin >> x;
for (int j = 59; ~j; --j)
if (x >> j & 1) { S[j].push(x); break; }
} vector<ll> Ans; ll ans = 0;
while (1) {
bool ok = 0;
for (int i = 0; i < 60; ++i)
if (!(ans >> i & 1) && !S[i].empty()) {
ok = 1, Ans.push_back(S[i].top()), ans ^= Ans.back(), S[i].pop();
break;
}
if (!ok) break;
}
for (int i = 0; i < 60; ++i)
if (!S[i].empty()) return cout << "No\n", 0;
cout << "Yes\n";
for (auto u : Ans) cout << u << " "; cout << "\n";
return 0;
}
|