题解 | #A+B Problem#

用字典树做
预处理 每个数字前面都是0（2变为000002）
关键要处理好找到的字符串和原字符串是否一样
如果一样的话 只能继续找个不一样的 所以用fa数组记录每个节点的父亲 方便回去重新找


代码
#include<iostream>
#include<string>

using namespace std;

const int N = 1e5 + 5;
int n;
string ss[N];
int id;
int cnt[N];//以i号节点结尾的数出现的次数
int trie[N][10];
int fa[N];
string s2;
void create(string s) {
    int now = 0;
    for (auto it : s) {
        if (trie[now][it - '0'] == 0) {
            trie[now][it - '0'] = ++id;
            fa[id] = now;
        }
        now = trie[now][it - '0'];
    }
    cnt[now]++;
}

inline string find(string s) {
    string res;
    for (auto it : s)
        res += '9' - it + '0';
    return res;
}

string solve(string s) {
    //返回最接近s的字符串
    string res;
    int now = 0;
    for (int i = 0; i < 6; i++) {
        //对于每位数字
        int num = s[i] - '0';
        while (trie[now][num] == 0) {
            num = num ? num - 1 : 9;
        }
        res += '0' + num;
        now = trie[now][num];
        //cout << res << endl;
    }
    if (res == s2 && cnt[now] == 1) {
        //字符串重复  回溯找串
        int pos = 5;
        while (true) {
            int c = res.back() - '0';
            int num = c ? c - 1 : 9;
            res.pop_back();
            now = fa[now];
            while (num != c && trie[now][num] == 0) {
                num = num ? num - 1 : 9;
            }
            if (num == c) {
                pos--;
                continue;
            }
            else {
                res += '0' + num;
                pos++;
                now = trie[now][num];
                break;
            }
        }
        for (int i = pos; i < 6; i++) {
            int num = s[pos] - '0';
            while (trie[now][num] == 0)
                num = num ? num - 1 : 9;
            res += num + '0';
            now = trie[now][num];
        }
    }
    return res;
}

int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s1;
        cin >> s1;
        int len = s1.size();
        while (6 - len > 0) {
            ss[i] += '0';
            len++;
        }
        ss[i] += s1;
        create(ss[i]);
    }

    int black = 0;
    for (int i = 1; i <= n; i++) {
        s2 = ss[i];
        if (black)cout << " ";
        else black++;
        //找出ss[i]的最优解
        string s = find(ss[i]);
        string ans = solve(s);
        string res;
        for (int j = 0; j < 6; j++) {
            res += (ss[i][j] - '0' + ans[j] - '0') % 10 + '0';
        }
        int pos = 0;
        while (pos < 6 && res[pos] == '0')pos++;
        if (pos == 7)cout << 0;
        else cout << res.substr(pos);
    }
    return 0;
}