关于数位 DP 的一点点
关于数位 DP 的一点点
数位 DP 用于解决如下格式的问题：
给定一个闭区间 [L,R]，让你求这个区间中满足 某种条件 的数的总数。数位 DP 是一个很朴素的想法，其实就是枚举每一位的情况，再加了一个公共部分的缓存。
对于多组测试数据的题目，两组测试数据之间不用清缓存（因为缓存针对的是普遍情况，而边界情况是暴力统计不缓存的，所以缓存可以共用）。个人感觉，在数位 DP 的实现上
记忆化 DFS比DP要好写一点。
数位 DP 的一个特点是dfs(x, y, z)在(x, y, z)这个三元组确定的情况下是可以确定的，所以可以缓存下来。但是在边界情况时缓存不具有普遍性，于是暴力统计。数位 DP 干了一件这样的事情：暴力统计的枚举方式是 \operatorname{for} i \in [l,r]，没有公共部分，但是数位 DP 的统计方式是每一位确定过去，这使得它有一个优势，就是出现了大量的重复，可以进行优化。
【LightOJ 1140】How Many Zeroes?
题意
求区间 [m,n] 中的数字的十进制表示中总共有多少个 0
【HDU 2089】不要 62
题意
求区间 [m,n] 中，十进制表示中既不包含连续的 62，也不包含 4 的数的个数。
【HDU 3555】Bomb
题意
求区间 [1,N] 中数字的十进制表示包含连续 49 的数字个数
可以参考注释理解
【SPOJ BALNUM】Balanced Numbers
题意
在下列情况下，正整数被视为平衡数：
- 每个偶数数字在其十进制表示形式中出现奇数次
- 每个奇数数字在其十进制表示形式中出现偶数次
上面的翻译比较垃圾，大概理解一下
例如，77、211、6222 和 112334445555677 是平衡数，而 351、21 和 662 不是平衡数。
给定区间 [A,B]，求其中平衡数的个数。
可以参考注释理解
【SPOJ MYQ10】Mirror Number
题意
镜面对称数是仅包含 0、1 和 8 的回文数
求 [a,b] 中有几个镜面对称数
数据范围是 10^{44}，所以要开一个字符数组来存输入
并且特判一下 a 本身是不是回文数
如果需要编译运行，可以前往 Gist ᴮᵃᶜᵏᵘᵖ 复制公共头
如果编译器不支持 C++11，请将 constexpr 改为 const
