首页 > 代码库 > CodeVS 1359 数字计数 51nod 1042 数字0-9的数量 Pascal
CodeVS 1359 数字计数 51nod 1042 数字0-9的数量 Pascal
题目大意：
我的代码又臭又长，但是毕竟是我这个jr想了几天才推出的公式，看别的大神都写数位DP，所以我决定分享一下我的思路。我认为我的思路一向是最好理解的！
要分两种情况讨论：
1.0的情况。我们首先推出0~9中只有1个0，在0~99中有(1+(9*100*1))个0{第一位可以为1~9，第二位可以为0~9，0只可以放在后者，所以乘1}，在0~999中有((1+(9*100*1))+(9*101*2))个0~6666为例，先算出0~999中0的个数，在算出1000~5999中0的个数，则为(102*5*3)个0，再从6666中减去6000，继续进行运算。此时我们就可以不用特判第一位数的特殊情况。但是在这里0还有一种特殊情况，就是中间出现一个0，那么我们就要加上0之后的数，例如500233，搜到第二个0时，发现有2个连续的0，就要加上233*2。
2.1~9的情况。与0的推法差不多，就是先算出0~999中1~9的数量，再算出1000~5999中的数量，因为只到5000，所以5以后的不用加上1000，但6要加1。这里有一种情况与0的不相同，就是第一位数要加上这一数字的整十数。例如在0~999中，我们判断完第2~3位数之后，在1~9的情况中都要加上100。
最后加一个特判就完了。程序丑请不要吐槽。
const g:array[0..18] of int64=(1,10,100,1000,10000,100000,1000000,10000000,
100000000,1000000000,10000000000,
100000000000,1000000000000,10000000000000,100000000000000,
1000000000000000,10000000000000000,100000000000000000,100000000000000000);
type arr=array[0..9] of int64;
var n,m,num:int64;
Var i:longint;
var a,b:arr;
var c:string;
var r:arr;
function zero(x:int64;r:boolean):int64;
var ans,w,num,sum:int64;
Var i:longint;
var a:string;
begin
ans:=0;
if (x<10)then exit(1);
str(x,a);w:=length(a);
if r then
begin
num:=1;sum:=9;ans:=1;
for i:=2 to w-1 do begin inc(ans,num*sum);inc(sum,9);num:=num*10;end;
inc(ans,(x div g[w-1]-1)*g[w-2]*(w-1));
num:=0;
i:=2;while a[i]=‘0‘ do begin inc(num,x-x div g[w-1]*g[w-1] );inc(i);end;
inc(ans,num);
exit(ans+zero(x-x div g[w-1]*g[w-1],false));
end;
inc(ans,g[w-2]*(w-1)*(x div g[w-1])+g[w-1]);
num:=0;
i:=2;while a[i]=‘0‘ do begin inc(num,x-x div g[w-1]*g[w-1] );inc(i);end;
inc(ans,num);
exit(ans+zero(x-x div g[w-1]*g[w-1],false));
end;
procedure otn(var a:arr;x:int64);
var w,sum,num,ans:int64;
Var i,j:longint;
var a1:string;
begin
if x<10 then begin for i:=1 to x do inc(a[i]);exit;end;
str(x,a1);w:=length(a1);ans:=0;
for i:=1 to 9 do
begin
inc(a[i]);
sum:=9;num:=1;
for j:=2 to w-1 do
begin
inc(a[i],sum*num+g[j-1]);inc(sum,9);num:=num*10;
end;
inc(a[i],(x div g[w-1]-1)*g[w-2]*(w-1));
if (x div g[w-1]>i) then inc(a[i],g[w-1]);
if (x div g[w-1]=i) then
begin inc(a[i]);inc(a[i],x-x div g[w-1]*g[w-1]);end;
end;
otn(a,x-x div g[w-1]*g[w-1]);
end;
begin
read(n,m);a[0]:=zero(n,true);b[0]:=zero(m,true);
otn(a,n);otn(b,m);
str(n,c);
for i:=1 to length(c) do begin val(c[i],num);
if num<>0 then inc(r[num]);end;
if c[length(c)]=‘0‘ then inc(r[0]);
str(m,c);
for i:=2 to length(c)-1 do begin val(c[i],num);
if num=0 then inc(r[0])end;
for i:=0 to 9 do inc(b[i],r[i]);
for i:=0 to 9 do writeln(b[i]-a[i]);
end.
感谢观看！
CodeVS 1359 数字计数 51nod 1042 数字0-9的数量 Pascal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。