题意：http://www.lightoj.com/volume_showproblem.php?problem=1140
就是让你去查找L到R中0 的个数 但是不含有前导0
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<vector> #include<math.h> #include<string> using namespace std; #define INF 0x3f3f3f3f #define LL long long #define N 106 #define Lson rood<<1 #define Rson rood<<1|1 LL dp[20][20][20][2],d[20]; LL dfs(int now,int w,int tot,int falg,int fp) {///tot表示0的个数 但不包括前导0 falg为1表示是前导0但是要注意是否为一位数 if(now==1) return tot; if(!fp&&dp[now][w][tot][falg]!=-1) return dp[now][w][tot][falg]; LL ans=0; int ma=fp?d[now-1]:9; for(int i=0;i<=ma;i++) {///now-1==1时 表示现在判断的是一位数 int t=falg&&i==0&&now-1!=1;///判断是否为前导0并且额外注意到是否是最后一位 ans+=dfs(now-1,i,tot+(i==0&&!t),t,fp&&i==d[now-1]); } if(!fp) dp[now][w][tot][falg]=ans; return ans; } LL calc(LL x) { if(x==-1) return 0; if(x==0) return 1; LL xxx=x; int len=0; while(xxx) { d[++len]=xxx%10; xxx/=10; } LL sum=0; for(int i=0;i<=d[len];i++) {///如果只有1位数 那么数字0就算 所以就要判断 if(!i) sum+=dfs(len,i,len==1,1,i==d[len]); else sum+=dfs(len,i,0,0,i==d[len]); } return sum; } int main() { LL l,r; int T,t=1; scanf("%d",&T); while(T--) { scanf("%lld%lld",&l,&r); memset(dp,-1,sizeof(dp)); if(l>r) swap(l,r); printf("Case %d: %lld ",t++,calc(r)-calc(l-1)); } return 0; }
来源于@zhber