世界今亮点！【数位DP】计数问题

2023-03-21 15:09:23 来源：博客园

(相关资料图)

导读 ^ _ ^

数位DP

数位DP，即是对数的每一位进行统计操作的DP问题。

计数问题

思路（分类讨论）

首先，如果一遍遍枚举，显示是不行的，因为1e8次这样，明显会超时。这类问题的关键是分类讨论，以及如何去从划分的角度思考问题。这样一思考，我们的复杂度降至：10 (统计数) * 2（划分数）* 8（位数）* 1000（前导枚举数） = 160000。

进行分类讨论：

如下可知，我们要实现一个count的函数，以及一个power10函数。最终对结果进行累加即可。

代码实现

#include#include#includeusing namespace std;int power10(int x) {    //int res = 0;//这求幂得1啊！    int res = 1;    while(x--) res *= 10;    return res;}int getnum(vector& nums, int l,int r) {    int res = 0;    for(int i = l; i >= r; i--)         res = res*10 + nums[i];    return res;}int count (int n, int x) {        if(n == 0) return 0; //我们从1开始算的     vector nums;while(n) {nums.push_back(n%10);n /= 10;}n = nums.size();int res = 0;//从最高位开始枚举，如果查找的x为0，从第二位开始!x,并作处理。for (int i = n - 1 - !x; i >= 0; i--) {if(i < n - 1) {            res += getnum(nums,n-1,i+1) * power10(i);            if(!x) res -= power10(i);//去掉前导0        }        if(nums[i] == x) res += getnum(nums,i-1,0) + 1;        else if(nums[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++)    cout << count(b,i) - count(a-1,i) <<" ";cout << endl;}return 0;}

#谢谢你的观看！

^ _ ^

关键词：