数位统计DP
定义
数位DP（Digital DP）是一种用于解决与数字的数位相关问题的动态规划算法。它将数字的每一位看作一个状态，通过转移状态来计算满足特定条件的数字个数或其他相关统计信息。
运用情况
- 统计满足特定条件的数字个数，例如在给定范围内有多少个数字满足某些数位特征。
- 计算数字的某个数位上的特定统计信息，如出现的数字频率等。
- 解决与数字排列、组合相关的问题。
注意事项
- 数位DP的核心是正确定义状态和状态转移方程。状态的设计要能够简洁地表示问题的特征，并且状态转移要能够准确地反映数字的数位变化。
- 注意边界情况的处理，特别是对于最高位和最低位的特殊处理。
- 数位DP通常需要进行记忆化搜索或使用动态规划数组来避免重复计算，以提高效率。
- 在实际应用中，要根据具体问题的特点选择合适的数位DP方法，并进行适当的优化和剪枝。
解题思路
- 分析问题，确定需要统计的数字特征或满足的条件。
- 设计状态，通常使用一个多维数组来表示不同数位上的状态。
- 定义状态转移方程，描述如何从一个状态转移到另一个状态。
- 确定初始状态和边界条件。
- 使用记忆化搜索或动态规划算法来计算状态值。
- 根据最终的状态值得到问题的答案。
AcWing 338. 计数问题
题目描述
运行代码
#include <iostream>
#include <vector>
using namespace std;
int power(int x)
{
int res = 1;
while(x --)
res *= 10;
return res;
}
int get(vector<int> num, int l, int r)
{
int res = 0;
for(int i = l; i >= r; i -- ) res = res * 10 + num[i];
return res;
}
int count(int n, int x)
{
if(n == 0) return 0;
vector<int> num;
while(n)
{
num.push_back(n%10);
n/=10;
}
n = num.size();
int res = 0;
for(int i = n - 1 - !x; i >= 0; i --)
{
if(i < n - 1)
{
res += get(num, n - 1, i + 1) * power(i);
if(x == 0) res -= power(i);
}
if(num[i] == x) res += get(num, i - 1, 0) + 1;
else if(num[i] > x) res += power(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 < 10; i ++)
cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}代码思路
power函数：计算 10 的指定次幂。get函数：从给定的数字数组中，按照指定的范围（从左到右）提取出一个数字。count函数：这是核心函数，用于计算给定数字n中特定数字x出现的次数。它通过将数字n转换为数字数组，然后从高位到低位进行分析计算。对于每一位，如果该位小于最高位且不等于x，则加上前面高位构成的数字乘以 10 的相应次幂；如果该位等于x，则加上低位数字构成的数加 1；如果该位大于x，则加上 10 的相应次幂。最后返回总的出现次数。- 在
main函数中：不断读取两个数字a和b，如果都不为 0 则进行处理。通过交换确保a小于b，然后对于数字 0 到 9，分别计算在b中出现的次数减去在a-1中出现的次数，并输出。
改进思路
-
简化计数逻辑：当前的
count函数实现较为复杂，它通过手动处理每一位数字来统计特定数字x出现的次数。可以考虑简化这一过程，直接遍历范围内的每个数，统计相应数字出现的次数，这可能使逻辑更清晰。 -
避免重复计算：注意到
count函数对每个数字x从a到b都独立计算了一次，这导致了很多重复的工作，特别是对于连续的整数序列。可以通过计算每个数字在一个数位上的贡献，然后根据位数累加这些贡献，来减少重复计算。 -
使用字符串处理数字：将整数转换成字符串处理，在某些情况下可以使代码更加直观简洁，尤其是在需要频繁操作数字的每一位时。
-
预计算 powers of 10：当前
power10函数在每次调用时都重新计算10的幂，如果在循环外预先计算好所需的10的幂次方数组，可以提高效率。 -
优化输入处理：代码中通过
if(a > b) swap(a, b);确保了a<=b，但这个条件检查对于解决问题并非必要，因为统计数字出现的次数并不依赖于a和b的顺序。 -
利用STL中的容器和算法：比如，可以使用
std::unordered_map来存储每个数字出现的次数，利用标准库提供的函数来简化代码。