2分+记忆化搜索

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL m[20];
LL f[30][10][3];
LL dfs(LL x,bool flag,LL now,bool fff) {
    if(now>=3) fff=1;
    if(x==0) return fff;
    if(!flag&&f[x][now][fff]!=-1) return f[x][now][fff];
    LL MAX=flag?m[x]:9,ans=0;
    for(LL i=0; i<=MAX; i++) {
        if(i==6) ans+=dfs(x-1,flag&&(i==MAX),now+1,fff);
        else ans+=dfs(x-1,flag&&(i==MAX),0,fff);
    }
    if(!flag) f[x][now][fff]=ans;
    return ans;
}
LL work(LL x) {
    memset(m,0,sizeof(m));
    for(LL i=1; x; i++) {
        m[i]=x%10;
        x/=10;
    }
    return dfs(15,1,0,0);
}
LL k,T;
int main() {
    memset(f,-1,sizeof(f));
    cin>>T;
    while(T--) {
        cin>>k;
        LL l=0,r=500000000000,mid,ans=0;
        while(l<=r) {
            mid=(l+r)/2;
            if(work(mid)>=k) {
                ans=mid;
                r=mid-1;
            } else
                l=mid+1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}