Codefroces Round #863(div.3)---E

题目：Problem - E - Codeforces

题意：有一个序列a，a中的每个元素的每一位都不为4，问序列中第k个数字是多少。

分析：可以用数位dp查询出1-r中有多少个满足条件的数字，通过二分r找到结果。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int,pair<int,int>> pil;
typedef unsigned long long ULL;
const ll mod = 1e9+7;
const int M=1e5+5;
const int N = 3e5+ 5;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
int a[20],len=0;
ll f[20];
ll dfs(int pos,bool limit)
{
    if(!pos) return (ll)1;
    if(!limit&&f[pos]!=-1) return f[pos];
    ll res=0;
    int up=limit?a[pos]:9;
    for(int i=0;i<=up;i++)
    {
        if(i==4) continue;
        res+=dfs(pos-1,limit&&(i==up));
    }
    if(!limit) f[pos]=res;
    return res;
}
ll get(ll x)
{
    len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    memset(f,-1,sizeof(f));
    return dfs(len,true);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        ll k;
        cin>>k;
        ll l=k,r=1e18;
        while(l<r)
        {
            ll mid=(l+r)/2;
            if(get(mid)-1>=k) r=mid;
            else l=mid+1;
        }
        cout<<r<<endl;
    }
}