CodeForces 967E Big Secret 【异或】【贪心】

发表于 | 更新于 | 分类于

题目大意：

给出n个数，将它们重新排序，使得排序后的序列满足前n个数的异或值依次递增。

解题思路：

考虑这样一个问题，要使$p \bigoplus q > p$并且此时花费的p最小，用x代表p的二进制表示中从最低位往最高位处第一个不为0的位置，那么最小的q即为二进制表示中的x位是1且其余位都是0。
对于这个问题，我们以二进制表示中的最高位为区分点，先把所有数用一个容器存起来。取数时先看当前的数第一个为0的低位是否有对应的q满足要求，有的话就取，没有就继续往下找，这样依次取直到取完所有数或者满足不了要求为止。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int MAX = 1e5+5;

int n;
bool flag;
long long t, res[MAX];
vector<long long> G[64];
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%I64d", &t);
        for(int i = 60; i >= 0; --i)
        {
            if((t >> i) & 1)
            {
                G[i].push_back(t);
                break;
            }
        }
    }
    t = 0;
    for(int idx = 0; idx < n; ++idx)
    {
        flag = false;
        for(int i = 0; i <= 60; ++i)
        {
            if((t & (1ll << i)) == 0 && G[i].size())
            {
                res[idx] = G[i].back();
                t = t ^ G[i].back();
                G[i].pop_back();
                flag = true;
                break;
            }
        }
        if(flag == false)
            break;
    }
    if(flag)
    {
        puts("Yes");
        for(int i = 0; i < n; ++i)
            printf("%I64d ", res[i]);
    }
    else
        puts("No");
    return 0;
}
Donate comment here
0%