题目描述

难度分:$1900$

输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n-1$的数组$a(0 \leq a[i] \leq 2n)$。

构造一个长为$n$的，$0$到$n-1$的排列$b$，满足$a[i] = b[i] \oplus b[i+1]$。

输入保证有解。

输入样例$1$

4
2 1 2

输出样例$1$

0 2 3 1 

输入样例$2$

6
1 6 1 4 1

输出样例$2$

2 3 5 4 0 1 

算法

位运算

这个题主要就是分析性质，可以很容易发现$b[i]=b[1] \oplus \oplus_{j=1}^{i-1}a[j]=b[1] \oplus s[i-1]$，这样一来只要$b[1]$确定了，$b$数组的所有元素就确定了。由于题目保证有解，所以$s$数组的元素肯定是互不相同的，对于任意的$b[1]$，也肯定满足$b$数组的任意两个元素都不同，那么就只需要保证最大值$max_{i=1}^{n}b[i] \lt n$即可。

于是我们可以把$s$中的所有元素都放入01字典树，然后遍历$x \in [0,n)$。对于每个$x$，按位贪心看$s$中谁和$x$异或得到的值最大，这个最大值只要小于$n$，$x$就可以作为$b[1]$。

复杂度分析

时间复杂度

将$a$数组的前缀和插入到字典树中时间复杂度为$O(nlog_2A)$，获得$b[1]$的时间复杂度也是$O(nlog_2A)$。最后根据$b[1]$构造出$b$数组的时间复杂度为$O(n)$，所以整个算法的时间复杂度为$O(nlog_2A)$。由于$a[i] \leq 2n$，其中$A$最大也是$O(n)$级别。

空间复杂度

空间消耗的瓶颈就是字典树，每一位都有$0$和$1$两个分支，一共有$h$层，空间复杂度大概是$O(2^h)$，本题中$h \lt 20$。如果$h$较小，那么空间复杂度的瓶颈就在于$a$的前缀和数组$s$，它的空间消耗是铁的$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
int n, a, s[N];

class Node {
public:
    int pass, end;
    Node* nxt[2] = {NULL};
    Node() {
        pass = end = 0;
    }
};

class Trie {
public:
    const int MAX_HEIGHT = 20;
    Node* root;
    Trie() {
        root = new Node;
    }

    void insert(int x) {
        Node* cur = root;
        for(int i = MAX_HEIGHT; ~i; i--) {
            int bit = x>>i&1;
            if(!cur->nxt[bit]) {
                cur->nxt[bit] = new Node;
            }
            cur = cur->nxt[bit];
            cur->pass++;
        }
        cur->end++;
    }

    int query(int x) {
        Node* cur = root;
        int ans = 0;
        for(int i = MAX_HEIGHT; ~i; i--) {
            int bit = x>>i&1;
            if(cur->nxt[1 - bit]) {
                ans |= 1<<i;
                cur = cur->nxt[1 - bit];
            }else {
                cur = cur->nxt[bit];
            }
        }
        return ans;
    }
};

int main() {
    scanf("%d", &n);
    Trie* trie = new Trie();
    for(int i = 1; i < n; i++) {
        scanf("%d", &a);
        s[i] = s[i - 1]^a;
        trie->insert(s[i]);
    }
    int b1 = 0;
    for(int x = 0; x < n; x++) {
        if(trie->query(x) < n) {
            b1 = x;
            break;
        }
    }
    printf("%d ", b1);
    for(int i = 2; i <= n; i++) {
        printf("%d ", b1^s[i - 1]);
    }
    return 0;
}