给定一个数\(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),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; 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
相关资源：连接二值图像中断开的点