首页 > 代码库 > (计数器)NOIP模拟赛(神奇的数位DP题。。)
(计数器)NOIP模拟赛(神奇的数位DP题。。)
没有原题传送门。。
手打原题QAQ
【问题描述】
一本书的页数为N,页码从1开始编起,请你求出全部页码中,用了多少个0,1,2,…,9。其中—个页码不含多余的0,如N=1234时第5页不是0005,只是5。
【输入】
一个正整数N(N≤109),表示总的页码。
【输出】
共十行:第k行为数字k-1的个数。
这道题是一道很有意思的DP题。
我们先来看一看这道题目
就是求1~n这么多个数中有多少个X数字。
然后我们来看一看一个例子:
在1~10这10个数中,每个数字(0~9)都在个位数中出现了1次。
在1~100这100个数中,每个数字(0~9)都在十位数中出现了10次。
在1~1000这1000个数中,每个数字(0~9)都在百位数中出现了100次。
以此类推。
所以我们得出了规律
在1~10^n中,数字x在第n-1位中出现了10^n-1次
如求2516数字5出现的次数
首先在2511~2516中,数字5在个位数出现1次;
在1~2510中,数字5在个位数中出现251次
251+1=252;
在1~2500中,数字5在十位数中出现25*10=250次
在1~2000中,数字5在百位数出现了2*100=200次
但是没完!
在2500~2516这么多数中,数字5在百位数还出现了16+1=17次
因为千位数字为2,小于5,所以5不会出现在千位
所以数字5出现的总次数就是252+250+200+17=719次
所以对于任何一个数字X,计算法则如下
计算X在右数第i位出现的次数
则为:
a=X*10^(i-1);
若num[i]>X return a+10^(i-1)即开头全部都为X数字的
若num[i]<X return a;
若num[i]==x return a+num%(10^i)+1;
但是对于任何一个数,0不可能为首位。
所以在计算0只能计算到第n-1位(假设num的位数为n)
然后判断一下就可以搞出来啦!
#include<iostream> #include<cstdio> using namespace std; int qs,n,l; long long num[11]; long long tt[11]; long long ans[11]; int main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); scanf("%d",&n); qs=n; while(qs){ l++; num[l]=qs%10; qs/=10; } tt[1]=1; for(int i=2;i<=10;i++) tt[i]=tt[i-1]*10; qs=n; for(int i=l;i>=1;i--) { for(int j=0;j<=9;j++) ans[j]+=tt[i-1]*num[i]*(i-1); for(int j=0;j<num[i];j++) ans[j]+=tt[i]; ans[num[i]]+=qs%tt[i]+1; } for(int i=1;i<=l;i++) ans[0]-=tt[i]; for(int i=0;i<=9;i++) printf("%lld\n",ans[i]); fclose(stdin); fclose(stdout); return 0; }
(计数器)NOIP模拟赛(神奇的数位DP题。。)