Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目链接 题意：问区间[n,m]中，不含数字4，也不含数字串“62”的所有数的个数。
思路：可以转化成求区间[0,x]
第一次接触数位dp,参考了这几篇博客。
比较重要的前提：
¨对于一个小于n的数，肯定是从高位到低位出现某一位<n的那一位。
¨如 n = 58 n为十进制数。
¨ x = 49 此时x的十位<n
¨ x = 51 此时x的个位<n
¨有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。
这样之前的位确定了，之后的位就不受n的限制即从00…0~99…9，可以先预处理
以及写成递归形式代码会简洁很多，所以就写了递归形式。
更详细的解释参加代码注释。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月15日 星期二 18时04分46秒
4File Name :code/hdu/2089.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n,m;
34int dp[30][2];
35int digit[30];
36
37int dfs (int pos,bool preis6,bool limit) //pos表示从低到高的第几位，是从高位往低位递归的（也就是从左到又）
38 // preis6 表示上一个数字是否为6，
39 // limit表示该位置是否有限制。
40{
41// cout<<pos<<" "<<preis6<<" "<<limit<<" "<<endl;
42 if (pos==0) return 1; //到该位置表明找到了一个解.
43
44 int res = 0 ;
45 if (!limit&&dp[pos][preis6]!=-1) return dp[pos][preis6]; //如果不是limit位置，表示结果是通用的，而之前又算过的话，就可以直接调用这个结果。
46 int mx = limit?digit[pos]:9; //mx第pos位置能取到的最大的数字..如果不是limit,则可以0..9任意取。
47// cout<<"mx:"<<mx<<endl;
48
49 for ( int i = 0 ; i <= mx; i++)
50 {
51 if (i==4||(i==2&&preis6)) continue;
52 res += dfs(pos-1,i==6,limit&&i==mx);
53 //(limit&&i==mx)中limit的含义是。。如果当前一位不是limit位（即0..9可以随便取的位置）
54 //，那么之后的位置也一定不是limit位置。
55 //而i==mx部分的意思是，在当前位置的数字小于当前位置的数字能取的最大值（mx）之前，
56 //后面位的数字随便取也不会超过上界。
57 }
58
59 if (!limit) dp[pos][preis6]=res; //记忆化. 非limit位的结果才通用，不然没必要存。
60
61 return res;
62
63}
64int solve ( int n)
65{
66 ms(digit,0); //将数按照每一位存到digit数组中
67 int len = 0 ;
68 while (n)
69 {
70 digit[++len] = n % 10;
71 n/=10;
72 }
73
74 return dfs(len,false,true);
75
76}
77
78int main()
79{
80 #ifndef ONLINE_JUDGE
81 freopen("code/in.txt","r",stdin);
82 #endif
83
84 while (~scanf("%d %d",&n,&m))
85 {
86 if (n==0&&m==0) break;
87
88 ms(dp,-1);
89 int ans = solve (m)-solve(n-1);
90
91 printf("%d\n",ans);
92 }
93
94 #ifndef ONLINE_JUDGE
95 fclose(stdin);
96 #endif
97 return 0;
98}