把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

w

解：

大家都知道，数位DP难点不是DP的过程，而是求解的过程，将一个表示为abcdefg的数一一对应地求出结果才是最困难的……，也是可能会花一两个小时debug的，没有办法的事情。
没有办法就上板子吧，代码：
（原题目是求l到r中不含有“4”和“62”的数字数量）

代码也都注释了，递归函数第一位表示位数，第二位表示状态（数位DP一定要有可以表示成单个或多个数字的状态，否则也要用数论化简），状态数量根据题目来定，第三位表示这一位有没有到原数最高位，简单无脑。

嗯，简单无脑就不讲了吧。

其实这个DFS看似简单无脑，而且只能处理数个state之间的关系，但实际上上限非常之高，具体的变换可以根据题目进行应变，举个例子：

“求l到r内含有“13”而且可以整除13的数”

由于13不是3这种特殊数字而且本身太大，无法用直接求出来，只能通过同余来化简，那么和这个dfs有什么关系呢，很显然，这个dfs会遍历一个数的所有位，因此我多设置一个state2，最开始记录最高位的数字，到下一位的时候将其乘10，并加上本位数字，再模13，一直进行到最后一位，如果最后的模值是0则通过，否则不通过，而由于记忆化搜索的缘故，每位最多也就多了13个不同的state2，复杂度提高较小。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <stack>
#include <math.h>
#include <iostream>
#include <functional>
using namespace std;
#define pow(i) (1<<(i))
#define INF (1<<29)
#define mem(x) memset(x,0,sizeof(x))
#define mem1(x) memset(x,-1,sizeof(x))
typedef long long LL;
int dp[10][2];
int digit[20];
int dfs(int pos, bool state, bool fp)//pos为当前位数，state为当前状态[1]，fp为上一位是否到达上限的标志
{
	if (!pos)  //若计算到最后一位，return结果[2]。
		return 1;
	if (!fp && dp[pos][state] != -1) //若前一位不满足上限，并且dp[pos][state]已经确定，直接return，这里体现了记忆化搜索
		return dp[pos][state];
	int i, fpmax, ret = 0; //fpmax为当前循环的上限，ret为此时的值
	fpmax = fp ? digit[pos] : 9;  //若上一位到达上限，此时最多枚举到这一位的数值，否则枚举到最大[3]
	for (i = 0; i <= fpmax; i++)
	{
		if (i == 4 || state && i == 2)//根据题意，这里是若本位为4，或者上一位为6本位为2，则不满足
			continue;
		ret += dfs(pos - 1, i == 6, fp && i == fpmax);//否则继续递归下一位，根据题意判定state及fp[4]
	}
	if (!fp) //若前一位不是上限，即这一位可以到最大，则更新dp值[5]
		dp[pos][state] = ret;
	return ret;  //返回ret
}
int cal(int x)
{
	int i, len;
	len = 0;
	while (x) //求出每一位
	{
		digit[++len] = x % 10;
		x /= 10;
	}
	return dfs(len, 0, 1);
}
int main()
{
	int n, m;
	int i, j;
	while (scanf("%d %d", &n, &m) != EOF)
	{
		if (n == 0 && m == 0)
			break;
		mem1(dp);//dp数组初始化为-1.多组数据实际上只需一次初始化
		printf("%d\n", cal(m) - cal(n - 1)); //计算时由右届到左界减一
	}
	return 0;
}