[HDU3652]B-number

悠悠 2023-08-17 17:38 60阅读 0赞

#### 题面描述 ####

给定一个数\\(n\\),求\\(1~n\\)中所有满足以下条件的数的个数：  
1.该数中不包含"13"  
2.该数能被13整除

#### 输入格式 ####

输入包含多行，每行一个整数\\(n(1\\leq n \\leq 1000000000)\\)

#### 输出格式 ####

输出符合要求的数的数量

#### 样例 ####

##### 样例输入 #####

13  
100  
200  
1000

##### 样例输出 #####

1  
1  
2  
2

#### 题解 ####

常规的数位dp。

#include<bits/stdc++.h>
    #define int long long
    //#define local
    using namespace std;
    inline char get(){
        static char buf[30000],*p1=buf,*p2=buf;
        return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read(){
        register char c=get();register int f=1,_=0;
        while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
        while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
        return _*f;
    }
    int dp[100][200][100],digit[100];
    int check(int str,int i){//返回:0-->什么都没有，1-->已出现过1，2-->已出现过13 
        if(str==0){
            if(i==1)return 1;
            return 0;
        }
        else if(str==1){
            if(i==1)return 1;
            if(i==3)return 2;
            return 0;
        }
        return 2;
    }
    int dfs(int len,int fp,int rel,int str,int cd){
        if(len==-1)return rel==0&&str==2;
        if(!fp && ~dp[len][str][rel])return dp[len][str][rel];
        int fpmax=fp?digit[len]:9,ret=0;
        for(register int i=0;i<=fpmax;i++){
            ret+=dfs(len-1,fp&&i==fpmax,(rel*10+i)%13,check(str,i),str==2);
        }
        return fp?ret:dp[len][str][rel]=ret;
    }
    int f(int n){
        int len=0;
        while(n){
            digit[len++]=n%10;
            n/=10;
        }
        return dfs(len-1,1,0,0,0);
    }
    signed main(){
        #ifdef local
        freopen("1.txt","r",stdin);
        #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int b;
        memset(dp,-1,sizeof(dp));
        while(cin>>b){
            //cout<<"-->"<<b<<endl;
            printf("%d\n",f(b));
        }
        //cout<<f(1000)<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Chen574118090/p/11609108.html