|
|
##[$AcWing$ $338$. 计数问题](https://www.acwing.com/problem/content/description/340/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
给定两个整数 $a$ 和 $b$，求 $a$ 和 $b$ 之间的所有数字中 $0∼9$ 的出现次数。
|
|
|
|
|
|
例如，$a=1024，b=1032$，则 $a$ 和 $b$ 之间共有 $9$ 个数如下：
|
|
|
|
|
|
`1024 1025 1026 1027 1028 1029 1030 1031 1032`
|
|
|
|
|
|
其中 $0$ 出现 $10$ 次，$1$ 出现 $10$ 次，$2$ 出现 $7$ 次，$3$ 出现 $3$ 次等等…
|
|
|
|
|
|
**输入格式**
|
|
|
输入包含多组测试数据。
|
|
|
|
|
|
每组测试数据占一行，包含两个整数 $a$ 和 $b$。
|
|
|
|
|
|
当读入一行为 `0 0` 时，表示输入终止，且该行不作处理。
|
|
|
|
|
|
**输出格式**
|
|
|
每组数据输出一个结果，每个结果占一行。
|
|
|
|
|
|
每个结果包含十个用空格隔开的数字，第一个数字表示 $0$ 出现的次数，第二个数字表示 $1$ 出现的次数，以此类推。
|
|
|
|
|
|
**数据范围**
|
|
|
$0<a,b<100000000$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
1 10
|
|
|
44 497
|
|
|
346 542
|
|
|
1199 1748
|
|
|
1496 1403
|
|
|
1004 503
|
|
|
1714 190
|
|
|
1317 854
|
|
|
1976 494
|
|
|
1001 1960
|
|
|
0 0
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
1 2 1 1 1 1 1 1 1 1
|
|
|
85 185 185 185 190 96 96 96 95 93
|
|
|
40 40 40 93 136 82 40 40 40 40
|
|
|
115 666 215 215 214 205 205 154 105 106
|
|
|
16 113 19 20 114 20 20 19 19 16
|
|
|
107 105 100 101 101 197 200 200 200 200
|
|
|
413 1133 503 503 503 502 502 417 402 412
|
|
|
196 512 186 104 87 93 97 97 142 196
|
|
|
398 1375 398 398 405 499 499 495 488 471
|
|
|
294 1256 296 296 296 296 287 286 286 247
|
|
|
```
|
|
|
|
|
|
### 二、暴力法
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 10;
|
|
|
|
|
|
// 暴力法获取从1开始到n,有多少个指定的x,[类似于前缀和的思路]
|
|
|
// 从0到10的8次方，就是枚举每一位，一个测试点是 8*10^8,会超时，不可取
|
|
|
int force_count(int n, int x) {
|
|
|
int res = 0;
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int t = i;
|
|
|
while (t) {
|
|
|
if (t % 10 == x) res++;
|
|
|
t /= 10;
|
|
|
}
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int a, b;
|
|
|
//当读入一行为0 0时，表示输入终止，且该行不作处理,注意这里 a||b的使用方法
|
|
|
while (cin >> a >> b, a || b) {
|
|
|
if (a > b) swap(a, b); // 这题还玩小的在后，大的在前，需要我们用代码判断，shit!
|
|
|
//计算0--9的每一个数出现的次数
|
|
|
for (int i = 0; i <= 9; i++)
|
|
|
cout << force_count(b, i) - force_count(a - 1, i) << ' ';
|
|
|
cout << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
但是，本题数据范围太大了，$0<a,b<100000000$ 。
|
|
|
|
|
|
两个数字$a-b$之间，最多就有$10^8$个数字，每个数需要遍历每一位，就是一个数字需要遍历$8$次最多,一次的时间复杂度最高是:$10^8*8$,而且有多组测试数据,不出意外会$TLE$。
|
|
|
|
|
|
### 三、思考过程
|
|
|
|
|
|
如计算 $0 \sim 78501$ 中 <font color='red'><b>$5$</b></font> 出现的次数。 <font color='red'><b>【答案：$41502$】</b></font>
|
|
|
|
|
|
#### 枚举$5$的位置
|
|
|
|
|
|
1、如果$5$位于倒数第$1$位，形如：`xxxx5`，由于$7850$<font color='red'>$1$</font>当前数位$1$小于$5$，前面只能取$0\sim 7849$
|
|
|
#####<font color='red'>$5$为末位共$7850$个</font>
|
|
|
|
|
|
2、如果$5$位于倒数第$2$位，形如：`xxx5x`，由于$785$<font color='red'>$0$</font>$1$当前数位$0$小于$5$，前面只能取$0\sim 784$，末位就可以是$0\sim 9$,再加$10$个
|
|
|
|
|
|
#####<font color='red'>$5$为末二位共$785*10^1=7850$个【乘法原理】</font>
|
|
|
|
|
|
3、如果$5$位于倒数第$3$位，形如：`xx5xx`，由于$78$<font color='red'>$5$</font>$01$当前数位$5$等于$5$:
|
|
|
- 前面取$0\sim 77$，共$78$个；后面是$00 \sim 99$，共$100$个。乘法原理，就是$78*100=7800$个；
|
|
|
- 前面取$78$，后面取“$00$,$01$”；共$2$个。
|
|
|
#####<font color='red'>$5$为末三位共$78*10^2+2=7802$个</font>
|
|
|
|
|
|
4、如果$5$位于倒数第$4$位，形如：`x5xxx`，由于$7$<font color='red'>$8$</font>$501$当前数位$8$大于$5$，前面可取$0\sim 7$(共$8$个)，后面$0 \sim 999=1000$. 小计：$8*1000=8000$个
|
|
|
#####<font color='red'>$5$为末四位共$8*10^3=8000$个。</font>
|
|
|
|
|
|
5、如果$5$位于倒数第$5$位，形如：`5xxxx`，由于<font color='red'>$7$</font>$8501$当前数位$7$大于$5$，后面$0 \sim 9999$. 小计：$10000$个
|
|
|
#####<font color='red'>$5$为末五位共$1*10^5=10000$个。</font>
|
|
|
|
|
|
##### 合计： $7850+7850+7802+8000+10000=41502$
|
|
|
|
|
|
<font color='red' size=4><b>总结：枚举数字$x$出现的位置，按$x$与$n$在该位上的大小关系，分为大于、小于、等于三类讨论。</b></font>
|
|
|
|
|
|
* 数字`x`大于当前位上的数字
|
|
|
|
|
|
`x`前面数字 **乘以** $pow(10,$后面剩余位数$)$
|
|
|
|
|
|
* 数字`x`小于当前位上的数字
|
|
|
|
|
|
`x`前面数字加$1$ **乘以** $pow(10,$后面剩余位数$)$
|
|
|
|
|
|
* 数字`x`等于当前位上的数字
|
|
|
|
|
|
`x`前面数字加$1$ **乘以** $pow(10,$后面剩余位数$)$ **再加上** 后面的剩余数字再加$1$
|
|
|
|
|
|
|
|
|
### 四、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
int a, b;
|
|
|
|
|
|
// 统计数字n中存在x=[1,9]的个数情况
|
|
|
// 建议结合题解中 78501示例的流程进行代码理解和记忆
|
|
|
int count_x(int n, int x) {
|
|
|
int res = 0; // 结果
|
|
|
int t = n; // n的副本
|
|
|
int base = 1; // base=pow(10,?) 基数
|
|
|
while (t) { // 数位分离过程中讨论大小关系
|
|
|
// ① x大于当前数位
|
|
|
if (t % 10 < x) res += t / 10 * base; // t:最高位到当前位，t/10:最高位到当前位前一位
|
|
|
// ② x小于当前位,加1
|
|
|
else if (t % 10 > x)
|
|
|
res += (t / 10 + 1) * base;
|
|
|
// ③ x等于当前位
|
|
|
else
|
|
|
res += t / 10 * base + (n % base + 1); // 后面的剩余数字+1
|
|
|
|
|
|
// 数位分离
|
|
|
t /= 10; // 前一位
|
|
|
base *= 10; // 变基
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
对于0，稍作修改，
|
|
|
此时只需分成两类，因为不存在当前为小于0的情况，不过每次的最高位要排除全0的情况。
|
|
|
*/
|
|
|
int count_0(int n) {
|
|
|
int res = 0; // 结果
|
|
|
int t = n; // n的副本
|
|
|
int base = 1; // base=pow(10,?)
|
|
|
while (t) { // 数位分离过程中讨论大小关系
|
|
|
// ① 当前位等于0
|
|
|
if (t % 10 == 0) res += (t / 10 - 1) * base + (n % base + 1);
|
|
|
// ② 当前位大于0
|
|
|
else
|
|
|
res += (t / 10) * base;
|
|
|
|
|
|
// 数位分离
|
|
|
t /= 10; // 前一位
|
|
|
base *= 10; // 变基
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
// 输入多组数据，以a=0,或b=0视为终点
|
|
|
while (cin >> a >> b, a || b) {
|
|
|
if (a > b) swap(a, b); // 这题还可以输入反着的，无聊~
|
|
|
cout << count_0(b) - count_0(a - 1) << " "; // 单独计算数字0计算结果
|
|
|
for (int i = 1; i <= 9; i++) // 输出数字1~9的计算结果
|
|
|
cout << count_x(b, i) - count_x(a - 1, i) << " ";
|
|
|
cout << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 五、数位$DP$ 模板
|
|
|
[猛击这里](https://www.cnblogs.com/littlehb/p/15796143.html)
|
|
|
|
|
|
### 六、$dfs$实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 32; // 2^{32}足够int用了
|
|
|
int a[N], al; // 数位分离拆开用的数组
|
|
|
int f[N][N]; // 第一维：第几位数；第二维：走到当前数位，已经取得了多少个
|
|
|
int n; // 当前枚举到的是哪个数
|
|
|
|
|
|
/**
|
|
|
u :从高到低，现在是第几位数
|
|
|
lead :是否考虑前导零
|
|
|
st :到当前深度已经出现n的个数
|
|
|
op :是否贴上界
|
|
|
返回值 :从当前数位u出发，在当前lead,st,op的前提下，可以得到多少个符合题意的数字
|
|
|
*/
|
|
|
int dfs(int u, int lead, int st, int op) {
|
|
|
if (!u) return st; // 递归出口,u==0时，所有数位计算完毕，al是从1开始计数的
|
|
|
if (!lead && !op && ~f[u][st]) return f[u][st]; // 非前导0 + 不贴上界 + 算过
|
|
|
|
|
|
// u位上的最大值
|
|
|
int up = op ? a[u] : 9; // 如果贴上界，则到op,否则可以全部取到
|
|
|
|
|
|
int res = 0; // 按上面三个条件lead,st,op走到u这个数位时，最终可以获取到多少个数呢？
|
|
|
for (int i = 0; i <= up; i++) {
|
|
|
int sum = st;
|
|
|
// ① 前面出现过非0数字 或者 本位置非0
|
|
|
// ② 当前数位是要查找的数字
|
|
|
if ((!lead || i > 0) && i == n) sum++;
|
|
|
// 如果原来是贴上界，现在继续贴上界，那么贴上界继续
|
|
|
res += dfs(u - 1, lead && !i, sum, op && i == a[u]);
|
|
|
}
|
|
|
|
|
|
// 记忆化
|
|
|
if (!lead && !op) f[u][st] = res;
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
int calc(int x) {
|
|
|
al = 0;
|
|
|
while (x) a[++al] = x % 10, x /= 10; // 高位在右,低位在左
|
|
|
// al :从al位开始
|
|
|
// lead :存在前导0
|
|
|
// st :前面填的数中数字n的个数是0个
|
|
|
// op :贴上界
|
|
|
return dfs(al, 1, 0, 1);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int l, r;
|
|
|
while (cin >> l >> r, l + r) { // l+r用的漂亮，只有两个都是0时，l+r才能是0，等同于 l || r
|
|
|
if (l > r) swap(l, r); // 谁大谁小还不一定，这题真变态
|
|
|
for (n = 0; n <= 9; n++) { // 0,1,2,3,...个数都有多少个
|
|
|
memset(f, -1, sizeof(f)); // 每轮需要初始化dp数组
|
|
|
cout << calc(r) - calc(l - 1) << ' ';
|
|
|
}
|
|
|
cout << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
### 七、答疑解惑
|
|
|
|
|
|
**$Q$:这句话怎么理解，为什么是返回$st$, 而不是返回$1$呢？**
|
|
|
```cpp {.line-numbers}
|
|
|
if (!u) return st;
|
|
|
```
|
|
|
|
|
|
**答**：当 $u$ 为$0$时，表示所有数位都已经递归完毕。此时， $st$ 记录了已经取得了多少个要查找的数字，也就是最终的答案。
|
|
|
|
|
|
因此，此时需要将 $st$ 作为函数的返回值，表示当前的递归子树所能取得的符合条件的数的个数。
|
|
|
|
|
|
在此题中，需要在数列中查找某个数字出现的次数，因此返回 $st$ 表示查询到的该数字在当前子树中出现的次数。
|
|
|
|
|
|
如果直接返回$1$，则表示该数字出现了一个，而没有考虑出现的次数，与题目要求不符 |
