题意
给一个数组b，问存不存在这些数的一个排列，使得这些数构造出来的另一个数组a严格上升。ai等于b数组前i个元素的异或值。
分析
假如数组b中有一些值为1的元素，那么某个1前面应该有偶数个奇数，否则构造出来的a数组就会下降。同理，假如数组b中有一些值为[2^k, 2^(k+1))的元素，那么某个值为[2^k, 2^(k+1))的元素前面应该有偶数个值大于2^(k+1) 且二进制形式在第k位值为1的元素，否则，构造出来的a数组也会下降。因此，我们可以通过前导0的个数给b数组中的元素分组，然后，在符合插入条件的情况下，前导0位数多的元素优先插入即可。
代码
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;
vector<ll> ans;
vector<ll> v[60];
ll n, d, t;
bool flag;
int main(void) {
if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
while(cin >> n) {
for(int i = 0; i < n; i++) {
scanf("%I64d", &d);
for(int j = 59; j >= 0; j--)
if(d >> j & 1) {
v[j].push_back(d);
break;
}
}
t = 0;
flag = true;
for(int j = 0; j < n && flag; j++) {
flag = false;
for(int i = 0; i < 60; i++) {
if(t >> i & 1 || v[i].empty())
continue;
ans.push_back(v[i].back());
t ^= v[i].back();
v[i].pop_back();
flag = true;
break;
}
}
if(ans.size() == n) {
printf("Yes\n");
for(int i = 0; i < n; i++)
printf("%I64d%c", ans[i], i == n - 1 ? '\n' : ' ');
}
else
printf("No\n");
}
return 0;
}
|