一、暴力大法
#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() {
//优化输入
ios::sync_with_stdio(false);
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\)个数字，每个\(10^8\)数，需要遍历每一位，就是一个数字需要遍历\(8\)次最多。
那就一次的时间复杂度最高就是:\(10^8*8\),而且有多组测试数据,不出意外会\(TLE\)。(这本来跑一次是可能过的，非得给多组数据，就是为了证明一下动态规划的强大，有意义吗~)
二、数学思维
既然暴力不行，那就只能靠数学思想解决问题：
如计算 \(78501\) 中 \(5\) 出现的次数。 【答案：\(41502\)】
枚举\(5\)的位置:
1、如果\(5\)位于倒数第\(1\)位，形如：xxxx5，由于\(7850\)\(1\)当前数位\(1\)小于\(5\)，前面只能取\(0\sim 7849\)；
\(5\)为末位共\(7850\)个。
2、如果\(5\)位于倒数第\(2\)位，形如：xxx5x，由于\(785\)\(0\)\(1\)当前数位\(0\)小于\(5\)，前面只能取\(0\sim 784\)，末位就可以是\(0\sim 9\),再加\(10\)个；
\(5\)为末二位共\(785*10^1=7850\)个。【乘法原理】
3、如果\(5\)位于倒数第\(3\)位，形如：xx5xx，由于\(78\)\(5\)\(01\)当前数位\(5\)等于\(5\)，前面取\(0\sim 77\)，共\(78\)个；后面是\(00 \sim 99\)，共\(100\)个。乘法原理，就是\(78*100=7800\)个；还需要继续加上前面取\(78\)，后面取“\(00\),\(01\)”；总计：\(7802\)个。
\(5\)为末三位共\(78*10^2+2=7802\)个。
4、如果\(5\)位于倒数第\(4\)位，形如：x5xxx，由于\(7\)\(8\)\(501\)当前数位\(8\)大于\(5\)，前面可取\(0\sim 7\)(共\(8\)个)，后面\(0 \sim 999=1000\). 小计：\(8*1000=8000\)个
\(5\)为末四位共\(8*10^3=8000\)个。
5、如果\(5\)位于倒数第\(5\)位，形如：5xxxx，由于\(7\)\(8501\)当前数位\(7\)大于\(5\)，后面\(0 \sim 9999\). 小计：\(10000\)个
\(5\)为末五位共\(1*10^5=10000\)个。
合计： \(7850+7850+7802+8000+10000=41502\)
总结：枚举数字\(x\)出现的位置，按\(x\)与\(n\)在该位上的大小关系，分为大于、小于、等于三类讨论。
-
数字
x大于当前位上的数字x前面数字 乘以 \(pow(10,\)后面剩余位数\()\) -
数字
x小于当前位上的数字x前面数字加\(1\) 乘以 \(pow(10,\)后面剩余位数\()\) -
数字
x等于当前位上的数字x前面数字加\(1\) 乘以 \(pow(10,\)后面剩余位数\()\) 再 加上 后面的剩余数字再加\(1\)!
三、实现代码
#include <bits/stdc++.h>
using namespace std;
int a, b;
//统计数字n中存在x=[1,9]的个数情况
int count_x(int n, int x) {
int res = 0;//结果
int t = n; //n的副本
int p = 1; //base=pow(10,?)
//数位分离过程中讨论大小关系
while (t) {
//x大于当前位
if (t % 10 < x) res += t / 10 * p;
//x等于当前位
else if (t % 10 == x) res += t / 10 * p + (n % p + 1);//后面的剩余数字+1
//x小于当前位,加1
else res += (t / 10 + 1) * p;
//继续数位分离
t /= 10; //进入前一位
p *= 10; //计算需要乘几个10的变量
}
return res;
}
/**
对于0，稍作修改，
此时只需分成两类，因为不存在当前为小于0的情况，不过每次的最高为要排除全0的情况。
*/
int count_0(int n) {
int res = 0;//结果
int t = n;//n的副本
int p = 1; //base=pow(10,?)
//数位分离过程中讨论大小关系
while (t) {
//当前位等于0
if (t % 10 == 0) res += (t / 10 - 1) * p + (n % p + 1);
//当前位大于0
else res += (t / 10) * p;
//继续数位分离
t /= 10; //进入前一位
p *= 10; //计算需要乘几个10的变量
}
return res;
}
int main() {
//优化输入
ios::sync_with_stdio(false);
//输入多组数据，以a=0,或b=0视为终点
while (cin >> a >> b) {
//如果有一个是0，那么输入结束
if (a == 0 || b == 0) break;
//这题还可以输入反着的，无聊~
if (a > b) swap(a, b);
//输出数字0计算结果
printf("%d ", count_0(b) - count_0(a - 1));
//输出数字1~9的计算结果
for (int i = 1; i <= 9; i++)
printf("%d ", count_x(b, i) - count_x(a - 1, i));
printf("\n");
}
return 0;
}