一道找规律数位DP好题
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int g[11],z[11],a[11],cntl[11],cntr[11];
int dp(int now,int t,int p,int x)
{
if(now==1)
{
if(a[now]>=p)return 1;
return 0;
}
int ans=0;
if(a[now]>p)ans=t;
else if(a[now]==p)ans=x%t+1;
ans+=a[now]*g[now-1];
ans+=dp(now-1,t/10,p,x%t);
return ans;
}
void work(int x,int *cnt)
{
if(!x){for(int i=0;i<=9;i++)cnt[i]=0;++cnt[0];return ;}
int len=0,val=x;
while(x)a[++len]=x%10,x/=10;
int t=1;for(int i=1;i<len;i++)t*=10;
for(int i=1;i<=9;i++)cnt[i]=dp(len,t,i,val);
cnt[0]=z[len-1]+(a[len]-1)*g[len-1];
if(len-1)cnt[0]+=dp(len-1,t/10,0,val);
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
for(int i=1,t=1;i<=9;i++,t*=10)g[i]+=10*g[i-1]+t;
z[0]=1;z[1]=1;
for(int i=2,t=9;i<=9;i++,t*=10)z[i]+=z[i-1]+(i-1)*t;
//work(1004,cntl);
//for(int i=0;i<=9;i++)printf("%d ",cntl[i]);puts("");
int l,r,T=0;
while(qr(l),qr(r),l&&r)
{
if(l>r)swap(l,r);
work(l-1,cntl);work(r,cntr);
for(int i=0;i<=9;i++)printf("%d ",cntr[i]-cntl[i]);puts("");
}
return 0;
}
最后一次更新于2019-11-14
0 条评论