AcWing 338. 计数问题
原题链接
中等
作者:
最后五分钟
,
2025-04-02 22:19:13
· 江西
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=45;
int shi[20],f[N];
int ans1[10],ans2[10];
void dp(int t,int ans[])
{
vector<int> nums;
while(t)nums.push_back(t%10),t/=10;
for(int i=nums.size()-1;~i;i--)
{
int x=nums[i];
for(int j=0;j<=9;j++)ans[j]+=f[i]*x;
for(int j=0;j<x;j++)ans[j]+=shi[i];
int tp=0;
ans[0]-=shi[i];
for(int j=i-1;~j;j--)tp=tp*10+nums[j];
ans[x]+=tp+1;
}
return;
}
void init()
{
shi[0]=1;
for(int i=1;i<=18;i++)shi[i]=10*shi[i-1];
f[0]=0;
for(int i=1;i<=18;i++)
f[i]=f[i-1]*10+shi[i-1];
}
signed sol(int ll,int rr)
{
int l=min(ll,rr),r=max(ll,rr);
memset(ans1,0,sizeof ans1);
memset(ans2,0,sizeof ans2);
dp(r,ans1);
dp(l-1,ans2);
for(int i=0;i<=9;i++)
cout<<ans1[i]-ans2[i]<<" ";
cout<<endl;
return 0;
}
signed main()
{
init();
int l,r;
while(cin>>l>>r,l&&r)sol(l,r);
return 0;
}