关于数位 DP 的一点点

关于数位 DP 的一点点

数位 DP 用于解决如下格式的问题:
给定一个闭区间 [L,R],让你求这个区间中满足 某种条件 的数的总数。

数位 DP 是一个很朴素的想法,其实就是枚举每一位的情况,再加了一个公共部分的缓存。
对于多组测试数据的题目,两组测试数据之间不用清缓存(因为缓存针对的是普遍情况,而边界情况是暴力统计不缓存的,所以缓存可以共用)。

个人感觉,在数位 DP 的实现上 记忆化 DFSDP 要好写一点。
数位 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

题面 ᴮᵃᶜᵏᵘᵖ

题意

在下列情况下,正整数被视为平衡数

  1. 每个偶数数字在其十进制表示形式中出现奇数次
  2. 每个奇数数字在其十进制表示形式中出现偶数次

上面的翻译比较垃圾,大概理解一下

例如,772116222112334445555677 是平衡数,而 35121662 不是平衡数。

给定区间 [A,B],求其中平衡数的个数。

代码 ᴮᵃᶜᵏᵘᵖ

可以参考注释理解

【SPOJ MYQ10】Mirror Number

题面 ᴮᵃᶜᵏᵘᵖ

题意

镜面对称数是仅包含 018 的回文数

[a,b] 中有几个镜面对称数

代码 ᴮᵃᶜᵏᵘᵖ

数据范围是 10^{44},所以要开一个字符数组来存输入
并且特判一下 a 本身是不是回文数


如果需要编译运行,可以前往 Gist ᴮᵃᶜᵏᵘᵖ 复制公共头

如果编译器不支持 C++11,请将 constexpr 改为 const

0.webp

热门博文