好的,这是一份针对题目 P1554 [USACO06DEC] 梦中的统计 Dream Counting B 的简易题解和代码注释。
简易题解
题目大意
给定两个整数 \(M\) 和 \(N\)(\(1 \le M \le N \le 2 \times 10^9\),且 \(N-M \le 5 \times 10^5\))。我们需要统计在从 \(M\) 到 \(N\)(包括 \(M\) 和 \(N\))的所有整数中,每个数字(\(0\) 到 \(9\))出现的总次数。
思路分析
由于 \(N-M\) 的范围较小,最大为 \(5 \times 10^5\),这意味着我们要处理的数字的数量不会太多。因此,我们可以采用最直接的模拟方法:遍历从 \(M\) 到 \(N\) 的每一个整数,然后对于每一个整数,逐位取出它的每一位数字,并对该数字的出现次数进行统计。
具体步骤如下:
- 创建一个数组(例如
cnt[10]
)来存储每个数字 \(0\) 到 \(9\) 的出现次数,并初始化为 \(0\)。 - 从 \(M\) 开始,循环到 \(N\)。对于每一个当前数字
i
:
a. 使用一个临时变量j
存储i
的值。
b. 如果j
为 \(0\),则数字 \(0\) 出现一次(注意题目数据范围 \(M \geq 1\),所以这里不用特殊处理i=0
的情况,但如果包含 \(0\),需要考虑)。
c. 当j
大于 \(0\) 时,循环执行以下操作:
i. 取出j
的个位数字:digit = j % 10
。
ii. 将cnt[digit]
加 \(1\)。
iii. 将j
除以 $10(即
j /= 10),去掉已经统计过的个位。 d. 重复 c 步骤直到
j` 变为 \(0\)。 - 循环结束后,依次输出
cnt[0]
到cnt[9]
的值即可。
示例说明
以输入 129 137
为例:
- 129:
1
出现 1 次,2
出现 1 次,9
出现 1 次 - 130:
1
出现 1 次,3
出现 1 次,0
出现 1 次 - 131:
1
出现 2 次,3
出现 1 次 - 132:
1
出现 1 次,3
出现 1 次,2
出现 1 次 - 133:
1
出现 1 次,3
出现 2 次 - 134:
1
出现 1 次,3
出现 1 次,4
出现 1 次 - 135:
1
出现 1 次,3
出现 1 次,5
出现 1 次 - 136:
1
出现 1 次,3
出现 1 次,6
出现 1 次 - 137:
1
出现 1 次,3
出现 1 次,7
出现 1 次
汇总后,得到输出 1 10 2 9 1 1 1 1 0 1
。
代码注释
#include<bits/stdc++.h> // 包含所有标准库,方便快速编程
using namespace std; // 使用标准命名空间int cnt[15]; // 定义一个大小为15的整型数组,用于存储0-9每个数字出现的次数。// 实际上只需要10个元素(cnt[0]到cnt[9]),多开一些空间不影响。int main()
{int n,m; // 定义两个整型变量n和m,用于存储输入范围的上下界。cin>>n>>m; // 从标准输入读取n和m的值。注意,这里m是区间的右端点,n是左端点,与题目描述的M和N一致。// 遍历从n到m(包括n和m)的每一个整数for(int i=n;i<=m;i++) {int j=i; // 使用一个临时变量j来存储当前数字i,以便在取位过程中修改j而不影响i。// 如果当前数字是0,由于题目保证 M >= 1,所以这里的 i 不会是0。// 但是如果 M 可以是0,那么 for 循环第一次 i=0 的时候,while(j) 会不执行,// 导致0的统计漏掉。所以需要额外判断 `if (j == 0) cnt[0]++;`。// 但对于本题,M>=1,所以数字0只会在多位数中出现。while(j) // 当j不为0时,循环执行,逐位取出j的数字。{cnt[j%10]++; // 取出j的个位数字 (j % 10),并将其对应的计数器加1。j/=10; // 将j除以10,去掉已经处理过的个位数字,以便处理下一位。}}// 遍历0到9,输出每个数字的出现次数for(int i=0;i<=9;i++) cout<<cnt[i]<<" "; // 打印每个数字的计数,并用空格隔开。return 0; // 程序正常结束。
}