Codeforces Round 863 (Div. 3) E. Living Sequence

题目链接

头一回用不是正解的方法做出来，也是比较极限，直接说做法就是二分+数位dp
数位$dp$ 求$1-n$出现多少含$4$的数字个数 $\sout{这纯纯板子了}$
设 $f(x)$ 为$1-x$ 中含有4的个数，$f$ 关于 $x$ 单调递增(并非严格) ,题目要找的其实是 $x-f(x)=k$这样一个解,我们去二分 $x$，检查 $x-f(x)$ 和 $k$ 的大小关系
Specially ，我们需要注意 $x-f(x)$ 是一个一会儿单调递增，一会儿没有增量的一个函数，所以我们要找最小的符合上述方程的解

#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
i64 k;
int len,a[20];
i64 dp[20][2][2];

i64 dfs(int pos,int limit,int flag){
    if(pos==len) return flag;
    if(dp[pos][limit][flag]!=-1) return dp[pos][limit][flag];
    int rg = limit?a[pos]:9;
    i64 ans = 0;
    for(int i = 0;i<=rg;++i){
        if(i==4) ans+=dfs(pos+1,limit&&i==rg,1);
        else ans+=dfs(pos+1,limit&&i==rg,flag);
    }
    return dp[pos][limit][flag] = ans;
}

void solve(){
    cin>>k;
    i64 l = k,r = 2e18;
    while(l<=r){
        i64 mid= (l+r)>>1;
        len = 0;
        i64 tmp = mid;
        while(tmp){
            a[len++] = tmp%10;
            tmp/=10;
        }
        reverse(a,a+len);
        for(int i = 0;i<20;++i){
            for(int j = 0;j<2;++j){
                dp[i][j][0]=dp[i][j][1]=-1;
            }
        }
        i64 t = dfs(0,1,0);
        if(mid-t>=k) r = mid-1;
        else l = mid+1;
    }
    cout<<l<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}