A+B Problem again

题面

链接：https://ac.nowcoder.com/acm/contest/30532/I
来源：牛客网

Komorebi是一个小学生，今天他需要学习加法。

老师给了同学们一个长度为 $n$ 的数组，然后要求同学们对于数组中的每一个数字 $A$，需要在数组中的其他数字中找到一个 $B$，使得 $A+B$ 最大。

但是，Komorebi并不知道加法需要"进位"，因此在这个问题中"A+B"中的"+"将不再进位，例如，Komorebi认为9+3=2，114514+1919810=1023324。

你能帮帮他完成作业吗？

输入描述:

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出描述:

输出一行 $n$ 个整数，第 $i$ 个整数表示以 $a_i$ 为 $A$ 可以得到的最大的 $A+B$，请注意这里的"+“是题目描述中设定的"特殊符号”。

输入样例 1

5
2 3 5 6 9

输出样例 1

8 9 8 9 5

样例说明 1

以 $A$ 取 $a_1=2$ 为例，当 $B$ 取 $a_2=3$ 时 $A+B=5$，取 $a_3=5$ 时 $A+B=7$ ，取 $a_4=6$ 时 $A+B=8$，取 $a_5 = 9$ 时 $A+B=1$，因此最大的 $A+B$ 是 8。

输入样例 2

3
10 10 1

输出样例 2

20 20 11

题解

字典树

每个数字最多有 6 个位，将其从高位到低位插入字典树。

每遍历一个数字，先将其从树中删除，再从高位到低位找到数中对应位与其"+"的最大值，累积到低位，得到该数的最大和结果。操作完成再将该数插回字典树。

代码

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
typedef pair<int, int> PII;
typedef long long LL;
// head

const int N = 1e5 + 5;
int pp[7] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int n, a[N], trie[10 * N][10], f[10 * N], tot = 1;

void insert(int x, int v) {
    int p = 1;
    f[p] += v;
    for (int i = 5; i >= 0; i--) {
        int ch = x / pp[i] % 10;
        if (trie[p][ch] == 0) trie[p][ch] = ++tot;
        p = trie[p][ch];
        f[p] += v;
    }
}

int find(int x) {
    int p = 1, s = 0;
    for (int i = 5; i >= 0; i--) {
        int ch = x / pp[i] % 10;
        int mv = -1, tp = 0;
        for (int j = 0; j <= 9; j++) {
            if (f[trie[p][j]] == 0) continue;
            int t = (ch + j) % 10;
            if (mv < t) {
                mv = t;
                tp = j;
            }
        }
        p = trie[p][tp];
        s = s * 10 + (ch + tp) % 10;
    }
    return s;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        insert(a[i], 1);
    }

    for (int i = 0; i < n; ++i) {
        insert(a[i], -1);
        printf("%d ", find(a[i]));
        insert(a[i], 1);
    }

    return 0;
}