1. 题目
2. 读题(需要重点注意的东西)
思路:
本题思路不难,主要还是需要分情况讨论清楚,此外,代码实现有边界情况,将思路转换成代码有点复杂。
主要的思路如下:
1、首先计数得分为计0的数
和计除0外的其他数
两种情况;
2、再而,又得针对前三位的取法分为恰好① 取abc
和② 取abc-1
~ 001(计0时)
or000 (计除0外的数)
具体的分类情况如下图所示:
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
/*
001~abc-1, 999
abc
1. num[i] < x, 0
2. num[i] == x, 0~efg
3. num[i] > x, 0~999
*/
// 获取num中以l开头,r结尾组成的数是多少,就是求思路中的“abc”
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;
}
// 求10的x次方
int power10(int x)
{
int res = 1;
while (x -- ) res *= 10;
return res;
}
// count函数用于计数 1 ~ n 中,x出现的次数
int count(int n, int x)
{
if (!n) return 0; // 如果n为0,返回0;因为我们统计的是从1~n中每个数出现的次数(注意数据范围取不到0的)
// num数组用于存储每一位上的数是多少(注意是倒着的,因此在下面for循环时,也是倒着遍历的)
vector<int> num;
// 如 n = 12345
// 则 num = {5,4,3,2,1}
while (n)
{
num.push_back(n % 10);
n /= 10;
}
// n此时表示原来n有多少位,然后用于计算i在每一位上的数有多少个
n = num.size();
// 计算i在每一位上的数有多少个
int res = 0;
// - !x的作用是,当x = 0时,要统计0在每一位上的数的个数,因为0不能在首位,所以此时 - !x = -1 ,即从第二位开始枚举
for (int i = n - 1 - !x; i >= 0; i -- )
{
// ---------------------------第 ① 种情况---------------------------
if (i < n - 1) // 当计数x = 0 时,枚举到最高位时,第①种情况是不存在的,因此需要i < n - 1特判一下
{
res += get(num, n - 1, i + 1) * power10(i);
if (!x) res -= power10(i); // 如果 x == 0,要减去在首位的计数
}
// ---------------------------第 ② 种情况---------------------------
// ② 中 第 Ⅰ 种情况,为0,不用写
if (num[i] == x) res += get(num, i - 1, 0) + 1; // 即 ② 中的第 Ⅱ 种情况 (d = x)
else if (num[i] > x) res += power10(i); // 即 ② 中的第 Ⅲ 种情况 (d > x)
}
return res;
}
int main()
{
int a, b;
while (cin >> a >> b , a)
{
if (a > b) swap(a, b); // 保证 b 是始终大于 a 的(因为题目中输入的第一个数 a 有可能大于第二个数 b )
// 计算的是b和a中i出现的次数
// 要求的是b到a之间的数的数,因此采用前缀和的思想,用b的计数-a的计数
for (int i = 0; i <= 9; i ++ )
cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}
可能存在的问题
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 动态规划
- 数位统计dp
6. 总结
线性dp的例题,理解思想并自行推导出代码。