题解 | #NIT的数#

1.先用数位dp求出小于x的回文有多少个
2.再加上k，就是求刚好有这么多个回文的数是多少
3.二分答案

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
ll x, k, f[20], p[15];
void init() {
    p[0] = 1;
    for (int i = 1; i < 15; i++)p[i] = 10ll * p[i - 1];
    for (int i = 2; i < 20; i++)f[i] = 9ll * p[i - 1 >> 1];
    f[1] = 10;
}
ll dp(ll x) {
    if (x >= 0 && x <= 9)return x + 1;// 把0也算上了
    ll res = 0;
    vector<int> v;
    while (x) {
        v.push_back(x % 10);
        x /= 10;
    }
    int n = v.size();
    ll a = 0, b = 0;
    for (int i = n - 1; i >= n >> 1; i--) {//求正好位数是n的回文数
        int x = v[i];
        res += p[i - n / 2] * (x - 1);//第一位不能为0
        if (i != n - 1)res += p[i - n / 2];
    }
    // 判断后半段是不是比前半段大，如果大，那么还有一个回文
    for (int i = n / 2 - 1; i >= 0; i--)
        b = b * 10 + v[i];
    for (int i = n + 1 >> 1; i < n; i++)
        a = a * 10 + v[i];
    if (b >= a)res++;
    // 加上1~n-1位数的回文数
    for (int i = 1; i < n; i++)
        res += f[i];
    return res;
}
int main() {
    init();
    cin >> x >> k;
    ll y = dp(x - 1) + k;//先求出小于x的回文数
    ll l = 1, r = 1e18;
    while (l < r) {
        ll mid = l + r >> 1;
        if (dp(mid) >= y)r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}