题目: 计数问题
题意:
给定两个整数 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
输入样例：
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0输出样例：
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思路:
- 首先我们明确题意，让我们找到09这十个数字在确定区间中出现的次数。暴力跑很简单，就是遍历区间，然后询问每个数字，看出现了哪些09的数，最后加在一起就好了。但是考虑到上亿级别的数据范围，暴力必然超时。
- 怎么优化？考虑数位dp。首先计算区间[A, B]，可以转化为计算[1, B] - [1, A-1]，可能有人会问，本来计算[A, B]都已经超时，现在计算两个区间不是更完蛋吗，这是因为当我们转化为求[1, B]之后，问题就开始变得简单了。
- 假设我们要计算0~9在区间[1, B]中的所有数字中出现的次数，因为每一位都可以取0~9，所以我们逐位来看。
- 设B这个数字是abcdefg，我们正在求d这一位的数字，考虑这样一种情况，前三位的值小于abc，那么显然d这一位可以取0~9任意值，而efg这三位取值范围是[000, 999]，显然此时d这一位无论取什么（不能取零，原因下面会说），都有[000，abc - 1] * [000, 999]种可能。
- 为什么不能取0？我们要明确一点，abcdefg是给定的区间的最大范围，而我们在自己构造一个小于这个值的数字，d是第四位，这里的四是从后向前数的，既然是我们自己构造的属于这个区间的数字，那么它就必须有意义，如果d取零，那么abc这三位就不能取000，必须从001开始，否则d这一位的0就失去意义了。
- 再考虑abc三位的取值就等于abc，那么显然d这一位的取值有三种情况，大于d，等于d或者小于d。
- 大于d显然超出了区间范围，不符合要求。
- 等于d时，后三位的取值范围是[000, efg]，从零开始，值是efg+1。
- 小于d时，后三位的取值范围是[000, 999]。
- 综上，将所有的取值可能加在一起就可以了。
- 另外要注意的一点是，当求最高位a取值范围时，a不能为零，原因同上。
- 此时我们就能理解，为什么求解两边[1, B]要比求解[A, B]更快，数位dp将整个区间的所有数字视为了一个数字。讨论一个数字各个位的所有可能。
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//还原num数组中，从l到r的数字
int get(vector<int>num,int l,int r)
{
int sum=0;
//从高位到低位
for(int i=l;i>=r;--i)//
{
sum=sum*10+num[i];
}
return sum;
}
//计算10^i
int power10(int n)
{
int sum=1;
for(int i=1;i<=n;++i)
{
sum*=10;
}
return sum;
}
//计算1到n中（n是个很大的数），x（x取值0~9）在所有数字中出现的次数之和。
int get_num(int n,int x)
{
//将n的每一位取出来存到数组中
vector<int>num;
while(n)
{
num.push_back(n%10);
n/=10;
}
n=num.size();
int res=0;
//i=n-1-!x等价于当i==n-1时判断x是否等于0，如果是就直接--i
for(int i=n-1-!x;i>=0;--i)//
{
//假设给定的数是abcdefg
if(i<n-1)
{
//如果当前位之前的数小于给定值，那么取值范围是 (000~abc) * (000~999)
res+=get(num,n-1,i+1)*power10(i);
//当我们在判断第i位时，如果第i位为零，那么是不能存在前导零的，否则第i位就没有意义了
//取值范围变为 (001~abc) * (000~999)
if(x==0)res-=power10(i);
}
//从000到efg，所以要＋1
if(num[i]==x)res+=get(num,i-1,0)+1;//
//如果当前位取值小于这一位的给定值，那么efg的取值范围是000~999
else if(num[i]>x) res+=power10(i);//
}
return res;
}
int main()
{
int a,b;
while(cin>>a>>b,a||b)
{
if(a>b)swap(a,b);
//依次计算0~9每个数字出现次数
for(int i=0;i<=9;++i)
{
//计算a到b，就是计算1到b减去1到a
cout<<get_num(b,i)-get_num(a-1,i)<<" ";//
}
puts("");//
}
return 0;
}
