题解：P10958 启示录

cff_0102 · 2024-12-11 09:36:29 · 题解

数位 dp 经典题，今天能在洛谷看到十分激动。

记忆化搜索实现的数位 dp 真的太好写也太好理解了吧。

代码中 l1,l2 分别为上一位和上上位是否为 6。

可以用二分找到对应的数。

不知道多久以前写的代码，十分易懂：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[20][2][2];
int a[20];
int dfs(int p,bool l2,bool l1,bool lim){
    if(p==-1)return 1;
    if(!lim&&dp[p][l2][l1]!=-1)return dp[p][l2][l1];
    int up=lim?a[p]:9;
    int s=0;
    for(int i=0;i<=up;i++){
        if(l2&&l1&&i==6)continue;
        s+=dfs(p-1,l1,i==6,lim && i==a[p]);
    }
    if(!lim)return dp[p][l2][l1]=s;
    return s;
}
int solve(int x){//返回 1-x 之间有几个非恶魔数 
    int p=0;
    while(x){
        a[p++]=x%10;
        x/=10;
    }
    return dfs(p-1,0,0,1);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    for(int i=0;i<20;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)dp[i][j][k]=-1;
    int t;cin>>t;
    while(t--){
        int n;cin>>n; 
        int l=665,r=9999999999ll;
        while(l<r){
            int mid=(l+r)>>1;
            if(mid+1-solve(mid)<n){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        cout<<l<<endl;
    } 
    return 0;
}