2004 - The Almost Lucky Numbers(Harder)
John and Brus believe that the digits 4 and 7 are lucky and all others are not. According to them, an almost lucky number is a number that contains at most one non-lucky digit in its decimal representation. Return the total number of almost lucky numbers between a and b, inclusive.
题目输入
Each line contains two integers a,b<=10^16
题目输出
For each line of input,output the total number of almost lucky numbers between a and b, inclusive.
输入/输出样例
题目输入
4 7 8 19
题目输出
4 4
C++解答
#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; ll dp[20][20][20][20]; ll l,r; int num[20],len; inline ll dfs(int i,int s,int p,int q,bool e,bool pre){ if(i==-1){ if(s<=1) return 1; return 0; } if(!e && dp[i][s][p][q]!=-1) return dp[i][s][p][q]; int v=(e?num[i]:9); ll ans=0; for(int j=0;j<=v;j++){ int news=s; if(j!=4&&j!=7){ if(j!=0||(!pre&&j==0)) news++; } ans+=dfs(i-1,news,p+(j==4),q+(j==7),e&&(j==v),(j==0&&pre)); } if(!e) dp[i][s][p][q]=ans; return ans; } inline ll solve(ll n){ if(n<0) return 0; if(n==0) return 1; len=0; while(n){ num[len++]=n%10; n/=10; } //for(int i=0;i<len;i++) printf("%d z\n",num[i]); return dfs(len-1,0,0,0,1,1); } int gao(ll w){ int a=0; while(w){ int b=w%10; w/=10; if(b!=4&&b!=7) a++; } return a; } int main(){ memset(dp,-1,sizeof(dp)); int ans=0; // printf("%d z\n",ans); while(~scanf("%lld%lld",&l,&r)){ printf("%lld\n",solve(r)-solve(l-1)); } return 0; }