ProblemCodeforces Round #477(Div. 2) E. Big Secret(贪心)

Codeforces Round #477(Div. 2) E. Big Secret(贪心)

题目连接:传送门

Description

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

Hint

N \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

我们倒着按位考虑。

先将所有数全都异或起来,那么我们需要依次选择这些数,使得异或出来的结果递减。

于是直接对当前已经异或出来的结果state从低位到高位贪心。假设当前考虑到第i位,那么我们只需看是否存在一个最高位为i的数还未被选。这样就能保证state递减,并且是最优的情况。如果在某一时刻不存在这样的i,那么无解

最后将记下来的数列翻转一下即为答案,时间复杂度O(N log \ max\{A_i\} )

Code

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

Categories: Problem Tags: ,

Comments

No Comments Yet. Be the first?

Post a comment