题目连接：传送门

Description

给你一个数列AA，求是否存在它的一个排列使得前缀异或和单调递增。如果存在，则输出一种方案

Hint

N≤105,Ai≤260N \leq 10^5, A_i\leq 2^{60}

Sample Input

6 4 7 7 12 31 61

Sample Output

Yes 4 12 7 31 7 61

Solution

我们倒着按位考虑。 先将所有数全都异或起来，那么我们需要依次选择这些数，使得异或出来的结果递减。 于是直接对当前已经异或出来的结果statestate从低位到高位贪心。 假设当前考虑到第i位，那么我们只需看是否存在一个最高位为i的数还未被选。 这样就能保证statestate递减，并且是最优的情况。 如果在某一时刻不存在这样的i，那么无解 最后将记下来的数列翻转一下即为答案，时间复杂度O(Nlog max{Ai})O(N log \ max\{A_i\} )

Code

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
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 100000 + 100;

int N;

struct node
{
    int val, h;
}A[Maxn];

inline int cmp (node a, node b) {return a.val < b.val;}

stack <int> S[70];
int Ans[Maxn];

main()
{
#ifdef hk_cnyali
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
#endif
    scanf("%lld", &N);
    int sum = 0;
    for (int i = 1; i <= N; ++i) scanf("%lld", &A[i].val), sum ^= A[i].val;

    for (int i = 1; i <= N; ++i)
    {
        int x = A[i].val;
        while (x)
            x >>= 1, A[i].h ++;
        S[A[i].h].push(i);
    }


    for (int i = 1; i <= N; ++i)
    {
        int a = sum, len = 1, pos = 0;
        while (a)
        {
            if ((a & 1) && !S[len].empty())
            {
                pos = S[len].top(); S[len].pop();
                break;
            }
            ++len;
            a >>= 1;
        }
        if (!pos)
        {
            cout<<"No"<<endl;
            return 0;
        }
        sum ^= A[pos].val;
        Ans[++Ans[0]] = A[pos].val;
    }
    reverse(Ans + 1, Ans + N + 1);

    cout<<"Yes"<<endl;
    for (int i = 1; i <= N; ++i) printf("%lld ", Ans[i]);
    puts("");
    return 0;
}