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; }