题目链接：点这里
【分析】
听大佬的建议，本人水的第一道数位dp，对dp的认识更深了。然而这个题依然是卡了好久。
我这里开的一个dp数组表示：dp[i][j]表示长度为i，第一位为j的符合情况的数量。然后就显然有：
dp[i][j]=0(j==4) dp[i][j]=dp[i-1][k](0=<k<=9&&(j!=6||k!=2))然后初始化一下dp。然后统计答案的时候从前往后累加就行。注意一点就是当当前位不符合情况的时候就不用继续往后累加了。在这wa了一次。
【代码】
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> #include<sstream> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define sin1(a) scanf("%d",&(a)) #define sin2(a,b) scanf("%d%d",&(a),&(b)) #define sll(a) scanf("%lld",&(a)) #define sll2(a,b) scanf("%lld%lld",&(a),&(b)) #define sdo(a) scanf("%lf",&(a)) #define sdo2(a,b) scanf("%lf%lf",&(a),&(b)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 #define uint unsigned int typedef pair<int,int> PII; #define A first #define B second #define pb push_back #define MK make_pair #define ll long long template<typename T> void read1(T &m) { T x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } m = x*f; } template<typename T> void read2(T &a,T &b) { read1(a); read1(b); } template<typename T> void read3(T &a,T &b,T &c) { read1(a); read1(b); read1(c); } template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } template<typename T> void outn(T a) { if(a>9) out(a/10); putchar(a%10+'0'); puts(""); } using namespace std; int dp[10][10]; int num[10]; void init(void) { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=7;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(j!=4&&(j!=6||k!=2)) dp[i][j]+=dp[i-1][k]; } int cal(int x) { int ret=0; int len=0; while(x) { num[len++]=x%10; x/=10; } num[len]=0; for(int i=len-1;i>=0;i--) {//num[i]表示当前位最大是多少 for(int j=0;j<num[i];j++) { if(num[i+1]!=6||j!=2) ret+=dp[i+1][j]; } if(num[i]==4||(num[i+1]==6&&num[i]==2))//这个条件加上表示后面的不用继续统计 break; } return ret; } int main() { init(); int n,m; while(read2(n,m),n||m) { outn(cal(m+1)-cal(n)); } return 0; }