数位dp

数位dp枚举0~n

#include<bits/stdc++.h>
using namespace std;
vector<int> a(11);
vector<int> b(11);
void dfs(int p, int limit, int length)
{
    if(p==length){
        for(int i=0; i<length; i++) cout<<b[i];
        cout<<endl;
        return ;
    }
    int up=limit?a[p]:9;
    for(int i=0; i<=up; i++){
        b[p]=i;
        dfs(p+1,limit&&i==up,length);
    }
}
void handle(int num)
{
    int p=0;
    while(num){
        a[p++]=num%10;
        num/=10;
    }
    reverse(a.begin(),a.begin()+p);
    dfs(0,1,p);
}
int main()
{
    handle(120);
    return 0;
}

带3的数

思路：先求不带3的数，再减去

#include<bits/stdc++.h>
using namespace std;
int f[15];
int dfs(int p, int limit, int length, vector<int> &a)
{
    if(p==length) return 1;
    int up=limit?a[p]:9;
    if(!limit&&f[p]!=0) return f[p];
    int ans=0;
    for(int i=0; i<=up; i++)
    {
        if(i==3) continue;
        ans+=dfs(p+1,limit&&i==up,length,a);
    }
    if(!limit)
    f[p]=ans;
    return ans;
}
int handle(int num)
{
    memset(f,0,sizeof(f));
    int x=num;
    vector<int> a;
    while(x)
    {
        a.push_back(x%10);
        x/=10;
    }
    reverse(a.begin(),a.end());
    for(auto x: a) cout<<x;
    cout<<endl;
    return num+1-dfs(0,1,a.size(),a);

}
int main()
{
    cout<<handle(200)-handle(100)<<endl;
    return 0;
}

带49的数

思路：先求不带49的数

#include<bits/stdc++.h>
using namespace std;
int f[22][10];
int dfs(int p, int pre, bool limit,vector<int>& v, int length)
{
    if(p==length) return 1;
    if(!limit&&f[p][pre]) return f[p][pre];
    int up=limit?v[p]:9;
    int ans=0;
    for(int i=0; i<=up; i++)
    {
        if(pre==4&&i==9) continue;
        ans+=dfs(p+1,i,limit&&i==up,v,length);
    }
    if(!limit) f[p][pre]=ans;
    return ans;    
}
int handle(int num)
{
    vector<int> a;
    int x=num;
    while(x)
    {
        a.push_back(x%10);
        x/=10;
    }
    reverse(a.begin(),a.end());
    return num+1-dfs(0,0,true,a,a.size());
}
int main()
{
    cout<<handle(500)<<endl;
    return 0;
}