个人觉得还比较好懂的理解,感觉本质是一个排列组合问题
问题一:前缀和思想
通过分别求出[1,a-1],[1,b]的各个数字次数,得出[a,b]的各个数字次数
问题二:分别求出每个数字在[1,n]中出现的次数
分类讨论
假设这个数字为 x
那么会出现:①abcxefg ②xbcdefg ③abcdefx
这三种情况,那么如何计算?
其实就是看x的左右两边有多少种排列组合
对于①来说需要计算左右两边,对于②需要计算右边,对于③需要计算左边
1. 首先对①进行讨论
(1) 当左边∈[ 000,abc-1]时,左边有abc种,右边可以取 [ 000 , 999 ], 也就是10^4种,一共abc*10^4种;
(2) 当左边=abc时:(相当于左边已经锁定为一种情况了)
1)d < x,0种,因为原数没得这么大的;
2)d==x, 那么右边可以取[000,efg], efg+1种;
3)d>x, 那么右边可以随便取[000,999],10^4种;
(1)+(2)加法原理即为最终答案
对特殊情况0进行讨论:
其实0就特殊在,
一是abc不能全为0:
即不能有000xefg,比如0000123,其实就是123,所以abc不能全为0,
不然x这个位置上的0就不会存在了,所以就是(1)中左边的情况变为abc-1种。
二是0不能在首位,道理与情况一一样,不合法表示。
2. 对②进行讨论
其实这个情况相当于(1)中的②,即左边锁定为1种情况了,只是①是abc,而②是啥也没有
3. 对③进行讨论
③其实也可以合并在①中,
相当于是:
①中(1)左边取[0…0,bcdefg-1],即bcdefg种,右边啥也没有也就是1种
(2)中同理,对于d>=x,右边都是一种情况,啥也没有
C++ 代码
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define ren(i,a,b) for(int i=a;i>b;i--)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define rene(i,a,b) for(int i=a;i>=b;i--)
#define debug(x) cout<<#x<<"="<<x<<endl;
using namespace std;
typedef long long ll;
const int N=10;
int a,b;
int get(vector<int>&a,int l,int r){
//高位到低位
int res=0;
for(int i=l;i>=r;i--){
res=res*10+a[i];
}
return res;
}
int pow10(int x){
int res=1;
while(x--){
res*=10;
}
return res;
}
int cnt(int n,int x){
if(n==0)return 0;
vector<int>a;
while(n){
a.push_back(n%10);
n/=10;
}
int num=a.size();
int res=0;
//最高位为 num-1,最低位为0
//枚举x在每一位上
//i=num-1-!x 实现0从第二位开始算
for(int i=num-1-!x;i>=0;i--){
//情况①中的(1)
res+=(get(a,num-1,i+1)-!x)*pow10(i);
//get(a,num-1,i+1)-!x, -!x对应情况0中-1
//情况②中的get(a,num-1,num)返回为0,所以可以直接合并于此,不用单独写if(i<num-1)
//情况③中的pow10(0)=1,get(a,num-1,1)即为abcdef;
//情况①中的(2)
if(a[i]>x)res+=pow10(i);
else if(a[i]==x)res+=get(a,i-1,0)+1;
}
return res;
}
void solve(){
while(cin>>a>>b,a||b){
if(a>b)swap(a,b);
for(int i=0;i<=9;i++){
cout<<cnt(b,i)-cnt(a-1,i)<<" ";
}
cout<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}