题解：CF923C Perfect Security

endswitch · 2024-08-19 15:43:22 · 题解

题意

有长度为 n 的数列 a,b，将数列 b 重新排列，使得数列 c 字典序最小，c_i = a_i \oplus b_i(1 \le i \le n)。

思路

异或、最小这两个关键字眼提醒我们此题是可以朝着 01 trie 的方向去思考的。

要使 c 序列字典序最小，那么越靠前的元素就一定越小，于是我们可以贪心地去做元素的查询。

那么应该如何查询呢？由于异或的性质，我们还是去贪心，每次从高位往低位尽量选和 a_i 二进制下相同的一位，01 trie 可以很好的维护。

时间复杂度 O(n\log V)，其中 \log V 是跑满的。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5 + 5;
int n, x, a[N];

namespace _01trie {
    const int V = 31;
    int tot;
    struct Trie {
        int sz, cnt, ch[2];

        inline int operator [] (const bool x) const {
            return ch[x];
        }
    } t[N << 5];

    inline void insert(int x) {
        int p = 0;

        for(int i = V - 1 ; ~ i ; -- i) {
            bool w = x & (1 << i);

            if(! t[p][w]) t[p].ch[w] = ++ tot;

            p = t[p][w],    ++ t[p].cnt;
        }
    }

    inline int query(int x) {
        int p = 0, res = 0;

        for(int i = V - 1 ; ~ i ; -- i) {
            bool w = x & (1 << i);

            if(! t[t[p][w]].cnt) w ^= 1;

            res = (res << 1) | w;

            p = t[p][w];

            -- t[p].cnt;
        }

        return res ^ x;
    }
}

using namespace _01trie;

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for(int i = 1 ; i <= n ; ++ i)
        cin >> a[i];
    for(int i = 1 ; i <= n ; ++ i) {
        cin >> x;

        insert(x);
    }

    for(int i = 1 ; i <= n ; ++ i)
        cout << query(a[i]) << ' ';

    return 0;
}