首页 > 其他 > 详细

第k个回文数

时间:2021-06-24 22:29:17      阅读:14      评论:0      收藏:0      [点我收藏+]
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
int num[20];
int dp[20][20][2];
int t[20];
ll dfs(int len,int cur,int s,bool lim)
{
    if(cur==0)return s;
    if(!lim&&~dp[len][cur][s])return dp[len][cur][s];
    int up=lim?num[cur]:9;
    ll res=0;
    for(int i=0;i<=up;i++){
        t[cur]=i;
        if(len==cur&&i==0)
            res+=dfs(len-1,cur-1,s,lim&&(i==up));
        else if(s&&cur<=(len+1)/2)
            res+=dfs(len,cur-1,t[len-cur+1]==i,lim&&(i==up));
        else res+=dfs(len,cur-1,s,lim&&i==up);
    }
    if(!lim)dp[len][cur][s]=res;
    return res;
}
ll calc(ll n){
    int len=0;
    while(n)num[++len]=n%10,n/=10;
    return dfs(len,len,1,1);
}
int main()
{
    memset(dp,-1,sizeof dp);
    ll a,k;
    cin>>a>>k;
    ll y=calc(a-1)+k;
    ll l=1,r=1e18+1;
    while(l<r){
        ll mid=l+r>>1;
        if(calc(mid)>=y)r=mid;
        else l=mid+1;
    }
    cout<<r;
}

  

第k个回文数

原文:https://www.cnblogs.com/qq1415584788/p/14928137.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!