[数位dp] 计数问题(模板题+数位dp)

0. 前言

数位 dp 目前见的比较少，最为经典的莫过于不要62，或许以前都是暴力求解。例如求解 1~n 中，数字 x 出现的次数这类题，暴力枚举每个数的时间复杂度为 $O(n)$，再枚举每一位的时间复杂度为 $lo{g}_{10}^n$，数字一大妥妥超时。

值得一提的是，2020 的蓝桥杯，第一道签到题就是暴力做法…

1. 数位dp 模板题

338. 计数问题

重点： 数位 dp、分情况讨论

问题分析及抽象：

该问题实际上是需要求解从 1~n 中 0,1,2,...,9 分别出现的次数。那么可实现一个 count(n, x) 函数，该函数可求出从 1~n 中所有数，数字 x 出现的次数。那么求解区间 [a,b] 的 x 出现的次数就可将问题转化为 count(b, x) - count(a - 1, x)。就是一个简单的前缀和思想。

例如：求解 1~n 中 x = 1 出现的次数，数字 n 的每一位以 abcdefg 代替，7 位数。

• 求 1 在第 4 位上出现的次数，即求 1 <= xxx1yyy <= abcdefg

  • 前三位 xxx = 000~abc-1， 则，yyy = 000~999 则一共是 abc * 1000 种选法
  • 前三位 xxx = abc，再分情况讨论
    • 当 d < 1，则，abc1yyy > abc0defg，则无法选择，0 种选法
    • 当 d = 1，则，yyy = 000~efg，共 efg + 1 种选法
    • 当 d > 1，则，yyy = 000~999，共 1000 种选法

• 注意： 以上分析只适用于 1~9 这些数字的数字个数。关于数字 0 的前导 0 问题，再下面的边界情况着重讨论。

• 边界情况：

  • 枚举数字 0 时，不能出现前导 0 的情况
  • 当 1 出现在最高位，则第一种情况不存在
  • 其它注意点在代码中进行了详细的注释，请查看！！！

• 时间复杂度是很低的，假设是个 8 位数字：

  • 需要算得 10 个数字分别出现的次数，10
  • 算出一个区间出现次数需要算两遍，2
  • 计算每一位，8
  • 求 abc、efg 这样的前缀需要循环或者预处理，8
  • 相乘则为 10 * 2 * 8 * 8 = 1280 次计算。暴力计算光是枚举 1~1e8 都已经超时了

这个题目其实不太经典…为什么将其归结为 dp 问题？这样理解 dp 本质上就是用某个具体的数，比如 f[i]，表示某一个集合，这里也是用某个数来表示某一个集合，所以这里将这道题归到了 dp 这一类。

并且这个题目的分情况讨论也是值得学习的。

往后的数位 dp 题目会正经一点…

代码：

// 例子 1~123456 求3出现的次数
// 第一位:最高位:3xxxxx 是不存在这种情况的,故贡献个数为 0
// 第二位:其实统计的是0~3~9999的情况,10000,0~3~9999 总共10000
// 第三位:统计的是00-11~3~000-999的情况,总共12*1000 = 12000,当前位是3,等于3,还需要123000~123456,456+1种情况
// 第四位:统计的是000-123-3-00~99的情况,总共123*100 = 12300,当前位是4,大于3,还需要123(4)300~123399,100种情况
// 第五位:统计的是0000-1234-3-9的情况,总共1234*10=12340,当前位是5,大于3,还需要1234(5)30~123439,10种情况
// 第六位:统计的是00000-12345-3的情况,总共12345,当前位是6,大于3,还需要123453~123433,1种情况
// 总的情况就是；10000+12000+12300+12340+12345+(456+1)+100+10+1=59553/*
#include <iostream>
using namespace std;int main() {int n = 123456, x = 3;int res = 0;for (int i = 1; i <= n; ++i) {int t = i;while (t) {if (t % 10 == x) ++res;t /= 10;}}cout << res << endl;        // 暴力输出59553，蓝桥杯签到题搞定hhreturn 0;
}
*/#include <iostream>
#include <algorithm>using namespace std;int get(vector<int> num, int l, int r) {    // 在此的l指的是原数字n的高位起始位置int res = 0;for (int i = l; i >= r; --i) res = res * 10 + num[i];return res;
}int power10(int x) {int res = 1;while (x --) res *= 10;return res;
}int count(int n, int x) {if (!n) return 0;vector<int> num;while (n) {num.push_back(n % 10);      // 逆序存储数字n的每一位数n /= 10;}n = num.size();int res = 0;for (int i = n - 1 - !x; i >= 0; --i) {                  // 从最高位到最低位依次枚举所有数位if (i < n - 1) {  int flag = get(num, n - 1, i + 1) * power10(i);  // 最高位不会出现情况1，如abcxdef，x不在最高位，则def可以从000~999共1000种取法res += get(num, n - 1, i + 1) * power10(i);      // 其中000~abc每一个数都可以对应1000种选法，则高位数字后乘以x后面的位数的10次方if (!x) res -= power10(i);                       // 如果当前枚举的是0,那么abc0edf，就需要从001~abc开始枚举，否则出现前导0if (x == 3) cout << flag << endl;}    if (num[i] == x) res += get(num, i - 1, 0) + 1;      // 当前位与枚举的x相等else if (num[i] > x) res += power10(i); }return res;
}int main() {int a, b;while (cin >> a >> b, a || b) {if (a > b) swap(a, b);for (int i = 0; i <= 9; ++i) count(b, i);cout << endl;}return 0;
}