Appearance
简介
如何统计区间
- 暴力算法,枚举
中的每一个整数,逐个判断是否满足条件,遇大数据必 gg。 - 优雅地使用 数位 DP。
问题
统计区间
预处理
采用「试填法」:从个位填到最高位,如果第
- 边界条件:
; - 计算顺序:
; - 时间复杂度:
。
cpp
int f[][];
for (int i = 0; i <= 9; i ++)
f[i][1] = 1; // 边界条件
for (int d = 2; d <= N; d ++) // N : 位数的上限,N ≈ log(r)
for (int i = 0; i <= 9; i ++)
for (int k = 0; k <= 9; k ++)
if (abs(k - i) >= 2)
f[i][d] += f[k][d - 1];
数位统计
考虑 前缀和 思想:
step 1
提取
cpp
int cap = 0, at[];
// cap : n 的位数;at[i] : n 的第 i 位数字
while (n)
at[++ cap] = n % 10, n /= 10;
step 2
所有
cpp
int ans = 0; // ans : 符合条件的个数
for (int d = 1; d < cap; d ++) // d : 位数
for (int i = 1; i <= 9; i ++) // i : 最高位填的数
ans += f[i][d];
step 3
统计所有
使用「试填法」,枚举
- 若
,该位不能填 ,只能填 。统计符合条件的情况; - 若
,该位只能填 . 统计符合条件的情况。 - 若此时
,下一位无论怎么填都不符合条件,跳出循环; - 若上一步未跳出循环且
,说明 本身也符合条件. 但「试填法」最多只填到 ,故还要多算一个。
- 若此时
cpp
// d : 当前填到第 d 位
for (int d = cap; d >= 1; d --) {
for (int i = (d == cap); i < at[d]; i ++)
if (abs(at[d + 1] - i) >= 2)
ans += f[i][d];
if (d != cap && abs(at[d + 1] - at[d]) < 2)
break;
if (d == 1)
ans ++;
}
模板
cpp
// 求 [0, n] 中有几个数符合条件
int dp(int n) {
// 特判
if (n <= 0) return !n;
int cap = 0, ans = 0, at[];
while (n)
at[++ cap] = n % 10, n /= 10;
for (int d = 1; d < cap; d ++)
for (int i = 1; i <= 9; i ++)
ans += f[i][d];
for (int d = cap; d >= 1; d --) {
for (int i = (d == cap); i < at[d]; i ++)
if (abs(last - i) >= 2) // 此处条件按照题目的需要
ans += f[i][d];
if (d != cap && abs(at[d + 1] - at[d]) < 2)
break;
if (d == 1)
ans ++;
}
return ++ ans;
}