传送门

---

题目大意

回文数字是指合法的字符串数字，然后是回文字符串。输出第 k ( k ≤ 1 0 100000 ) k(k \leq 10^{100000}) k(k≤10100000)个回文字符串。

解题思路

k k k这么大，显然是找规律的题目，那么不难发现回文数的个数应该按照位数来看，然后找到每个区间：

• 位数为 1 1 1： [ 0 , 9 ] [0,9] [0,9]共 10 10 10个；包含的个数区间为 [ 1 , 10 ] [1,10] [1,10]
• 位数为 2 2 2： [ 11 , 99 ] [11,99] [11,99]共 9 9 9个；包含的个数区间为 [ 11 , 19 ] [11,19] [11,19]
• 位数为 3 3 3： [ 101 , 191 ] , [ 202 , [ 292 ] , . . . , [ 909 , 999 ] [101,191],[202,[292],...,[909,999] [101,191],[202,[292],...,[909,999]共 90 90 90个；包含的个数区间为 [ 20 , 109 ] [20,109] [20,109]
• 位数为 4 4 4： [ 1001 , 1991 ] , [ 2002 , [ 2992 ] , . . . , [ 9009 , 9999 ] [1001,1991],[2002,[2992],...,[9009,9999] [1001,1991],[2002,[2992],...,[9009,9999]共 90 90 90个；包含的个数区间为 [ 110 , 199 ] [110,199] [110,199]
• 位数为 5 5 5： [ 10001 , 19991 ] , [ 20002 , [ 29992 ] , . . . , [ 90009 , 99999 ] [10001,19991],[20002,[29992],...,[90009,99999] [10001,19991],[20002,[29992],...,[90009,99999]共 900 900 900个；包含的个数区间为 [ 200 , 1099 ] [200,1099] [200,1099]
• 位数为 6 6 6： [ 100001 , 199991 ] , [ 200002 , [ 299992 ] , . . . , [ 900009 , 999999 ] [100001,199991],[200002,[299992],...,[900009,999999] [100001,199991],[200002,[299992],...,[900009,999999]共 900 900 900个；包含的个数区间为 [ 1100 , 1999 ] [1100,1999] [1100,1999]
• …

对于一个超大的给定的 k k k，我们需要首先确定它在哪个区间内，这个我们可以预处理每个区间的左端点（有规律的），然后分奇偶找每种区间的规律，对于第 i i i个长度为 x x x的区间， k − L i ∈ [ 0 , x − 1 ] k-L_i \in [0,x-1] k−Li​∈[0,x−1]，然后我们找规律发现：

• 若 i i i为奇数，那么将上面作差的结果对齐为 ⌊ d e l t a 2 ⌋ + 1 \lfloor \frac{delta}{2}\rfloor + 1 ⌊2delta​⌋+1，然后从左到右除第一位的每一位都是长度为 i i i位的答案从左到右的每一位，这里先不考虑回文的对称（第一位需要加上1）
• 若 i i i为偶数，那么将上面作差的结果对齐为 ⌊ d e l t a 2 ⌋ \lfloor \frac{delta}{2}\rfloor ⌊2delta​⌋，然后从左到右除第一位的每一位都是长度为 i i i位的答案从左到右的每一位，这里先不考虑回文的对称（第一位需要加上1）

对于第一步如何找到对应的左端点，我一开始写预处理，然后 M L E MLE MLE了，然后每次 O ( n ) O(n) O(n)去找，结果
T L E TLE TLE了，然后仔细观察，只需要看 k k k的位数会落在哪些区间——对于给定位数的数只可能在三个区间内，且是有规律的，那么我们每次都处理出这三个左端点看在哪个左端点的区间内即可。

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
const int maxn = 1e5 + 10;

string sub(string a, string b, int len) {  //大数减法
    int len1 = a.size(), len2 = b.size();
    string c = "";
    int cnt = len1 - len2;
    while (cnt--) c += '0';
    c += b;
    for (int i = len1 - 1; i >= 0; i--) {
        if (a[i] >= c[i]) {
            a[i] = (a[i] - '0') - (c[i] - '0') + '0';
        } else {
            int j = i - 1;
            while (j > 0 && a[j] == '0') j--;
            a[j] = (a[j] - '0') - 1 + '0', j++;
            while (j <= i) a[j] = (a[j] - '0') + 10 + '0', j++;
            a[i] = (a[i] - '0') - (c[i] - '0') + '0';
        }
    }
    string ans = "";
    int x = len1 - len;
    // cout << len << " " << x << endl;
    for (int i = x; i < len1; i++) ans += a[i];
    return ans;
}

inline int cmp(const string &s1, const string &s2) {
    if (s1.size() > s2.size()) return 1;
    if (s1.size() < s2.size()) return -1;
    for (int i = 0; i < s1.size(); i++) {
        if (s1[i] > s2[i])
            return 1;
        else if (s1[i] < s2[i])
            return -1;
    }
    return 0;
}

int pos;  //最后答案的长度
string L[5];

string Find(string s) {
    int len = s.size();
    L[1] = L[2] = L[3] = L[4] = "";
    L[1] += '2';
    for (int i = 1; i <= len - 2; i++) L[1] += '0';
    L[2] += "11";
    for (int i = 1; i <= len - 2; i++) L[2] += '0';
    L[3] += '2';
    for (int i = 1; i <= len - 1; i++) L[3] += '0';
    L[4] += "11";
    for (int i = 1; i <= len - 1; i++) L[4] += '0';
    for (int i = 1; i <= 3; i++) {
        if (cmp(s, L[i]) >= 0 && cmp(s, L[i + 1]) < 0) {
            pos = len * 2 - 4 + i;
            return L[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    string k;
    cin >> t;
    while (t--) {
        cin >> k;
        if (k.size() == 1) {
            cout << (char)(k[0] - 1) << ENDL;
            continue;
        }
        if (k == "10") {
            cout << "9" << ENDL;
            continue;
        }
        if (cmp(k, "11") >= 0 && cmp(k, "19") <= 0) {
            k[0] = k[1];
            cout << k << ENDL;
            continue;
        }
        string L = Find(k), res, temp = "", ans = "";
        //cout << L << " " << pos << endl;
        if (pos & 1) {
            res = sub(k, L, pos / 2 + 1);
            // cout << res << endl;
            temp += (res[0] - '0') + 1 + '0';
            for (int i = 1; i < res.size(); i++) {
                temp += res[i];
            }
            ans = temp;
            for (int i = temp.size() - 2; i >= 0; i--) ans += temp[i];
        } else {
            res = sub(k, L, pos / 2);
            // cout << res << endl;
            temp += (res[0] - '0') + 1 + '0';
            for (int i = 1; i < res.size(); i++) {
                temp += res[i];
            }
            ans = temp;
            for (int i = temp.size() - 1; i >= 0; i--) ans += temp[i];
        }
        cout << ans << ENDL;
    }
    return 0;
}