数位dp简单题
hdu3652
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;typedef long long ll;const int N = 10+10;int dig[N];ll dp[N][N][2][20];ll dfs(int len,int pre,int is,int sum,int f){if(len < 1) return is&&(sum==0) ;if(!f && dp[len][pre][is][sum]!=-1) return dp[len][pre][is][sum];int last = f ? dig[len] : 9;ll res = 0;for(int i=0;i<=last;i++){res += dfs(len-1,i,is||(pre==1&&i==3),(sum*10+i)%13,f&&(i==last) );}if(!f) dp[len][pre][is][sum] = res;return res;}ll solve(int n){int len = 0;while(n){dig[++len] = n % 10;n /= 10;}return dfs(len,0,0,0,1);}int main(){int t,n;ll ans;memset(dp,-1,sizeof(dp));while(scanf("%d",&n)!=EOF){ans = solve(n);printf("%lld\n",ans);}return 0;}hdu4722
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int N = 20+5;int dig[N];ll dp[N][20];ll dfs(int len ,int sum,int f){if(len<1) return sum%10==0;if(!f && dp[len][sum]!=-1) return dp[len][sum];int last = f ? dig[len] : 9;ll res = 0;for(int i=0;i<=last;i++){res += dfs(len-1,(sum+i)%10,f&&(i==last));}if(!f) dp[len][sum] = res;return res;}ll solve(ll n){if(n<0) return 0;int len = 0;while(n){dig[++len] = n%10;n/=10;}return dfs(len,0,1);}int main(){int t;int cas = 0;ll ans,l,r;cin>>t;memset(dp,-1,sizeof(dp));while(t–){scanf("%lld%lld",&l,&r);ans = solve(r) – solve(l-1);printf("Case #%d: %lld\n",++cas,ans);}return 0;}hdu 3555
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int N = 20+5;int dig[N];ll dp[N][10][2];ll dfs(int len ,int pre,int is,int f){if(len<1) return is;if(!f && dp[len][pre][is]!=-1) return dp[len][pre][is];int last = f ? dig[len] : 9;ll res = 0;for(int i=0;i<=last;i++){res += dfs(len-1,i,is||(pre==4&&i==9),f&&(i==last));}if(!f) dp[len][pre][is] = res;return res;}ll solve(ll n){int len = 0;while(n){dig[++len] = n%10;n/=10;}return dfs(len,0,0,1);}int main(){int t;ll ans,r;cin>>t;memset(dp,-1,sizeof(dp));while(t–){scanf("%lld",&r);ans = solve(r);printf("%lld\n",ans);}return 0;}
，没有什么可凭仗，只有他的好身体，没有地方可去，只想到处流浪。
