题目
思路
- 分情况讨论
$[a,b],0-9$
我们可以实现一个count函数:
$count(n,x)$,1~n中x出现的次数
最后的答案就是$count(b,x)-count(a-1,x)$ - 举例:
1~n,x=1
n=abcdefg
分别求出1在每一位上出现的次数
求1在第4位上出现的次数:
1<=xxx1yyy<=abcdefg
(1) 当xxx=000-(abc-1),yyy=000-999
总共有$abc\times1000$个数会在第4位上出现1
(2)当xxx=abc
2.1)当d<1,abc1yyy>abc0efg
这种情况不会有数在第4位上出现1
2.2)当d=1,0<=yyy<=efg
这种情况下会有$efg+1$个数会在第4位上出现1
2.3)当d>1,0<=yyy<=999
这种情况下会有1000个数会在第4位上出现1
所以该题的思路是:
+ 1)对每个a,b,在进一步处理前保持a<b(必要时,swap一下)
+ 2)实现一个函数count(n,i):计算1~n的是所有数中,数字i出现的次数
在count函数中:
算出整数n的总位数d(便于后面遍历)
从低位开始往高位遍历每一位:
取出当前遍历位的数dj
算出:以dj为分界,其左边的数的大小l,10的其右边的位数次方p,右边的数的大小r
需要的数据都有了,下面就可以分情况讨论计算结果了。
+ 3)在分情况讨论时,要格外注意当左边的数l为0的情况,以及当前的i为0的情况:当i为0时其左边整数不能为0
代码
摘自:https://www.acwing.com/solution/content/7128/
yyds!
#include<iostream>
#include<cmath>
using namespace std;
int dgt(int n) //计算整数n有多少位
{
int res=0;
while (n)
{
res++;
n/=10;
}
return res;
}
int count(int n,int i) //计算从1到n的整数中数字i出现多少次
{
int res=0,d=dgt(n);
for(int j=1;j<=d;j++) //从右到左第j位上数字i出现多少次(从右往左遍历)
{
// l和r是第j位左边和右边的整数 (视频中的abc和efg); dj是第j位的数字;
int p=pow(10,j-1),l=n/p/10,r=n%p,dj=n/p%10;
// 计算第j位左边的整数小于l (视频中xxx = 000 ~ abc - 1)的情况
if(i) res+=l*p; //i如果不是0的话,直接算
if(!i&&l) res+=(l-1)*p; // 如果i = 0, 左边高位不能全为0(视频中xxx = 001 ~ abc - 1)
// 计算第j位左边的整数等于l (视频中xxx = abc)的情况
if((dj>i)&&(i||l)) res+=p;
if((dj==i)) res+=r+1;
}
return res;
}
int main()
{
int a, b;
while(cin>>a>>b,a) //a不等于0
{
if(a>b) swap(a,b); //如果a比b大,交换a和b
for(int i=0;i<=9;i++)
cout<<count(b,i)-count(a-1,i)<<' ';
cout<<endl;
}
return 0;
}