注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1833】【Zjoi2010】【数字计数】  

2014-05-07 16:45:09|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:求[a,b]数码0~9各出现了多少次?

    一般都是把问题转化成 [1,b]出现的次数-[1,a-1]出现的次数0.0然后转化之后咱们怎么做?实际上问题就是求[1~n],0~9出现的次数。对于这个,咱们经常使用的方法便是数位DP。

     但是想到这里之后本来写了一些想法的,但是都比较零碎...然后...QAQ写不出程序出来...
     大家好0.0,咱是新一代的嘴巴选手z55哦呵呵呵呵呵呵...= =
     实际上咱们考虑一下,实际上就是对于所有的数分类...貌似有很多的分法额...咱是按最高位是多少来分的,实际上就是记录 n~100000..0,99999..9~100000..0....9~1,0的个数。
     比如 10234,咱们可以将所有的数分为:
    10234~10000,9999~1000,999~100,99~10,9~1。
     然后咱们一部分一部分处理

     对于9999~1000这种类型的,咱们可以转化成【9999~0000】的答案减去【999~000】的答案【后面就是强制使得开头一位为0】就可以非常迅速的算出来。999..[x个]~000..[x个],实际上每一个数码出现的次数就是10^(x-1)*x次【考虑把某个数放在某一位,然后其他位数的数显然可以随便填了】,然后这个就解决了。

     然后考虑n~10000...0,这就是数位dp了?这个咱们可以把所有的数按其从哪一位开始小于n的来分类,即,咱们从n的最高位开始,枚举从哪一位开始小于,然后咱们设n在那一位的值为c[i],咱们就枚举那一位为0~c[i]-1的情况【对于首位的要特判】,然后剩余的部分就是0000~9999的情况,处理掉,然后对于枚举的那一位也要加上去,然后对于之前的那几位也要加上。

    然后就可以了恩。
   PE一次...这题要注意最后一个9的不要有空格2333。
=====================

program bzoj1833;
var num:array[0..1,0..9]of int64;
    a,b:int64;
    shi:array[0..14]of int64;
    c:array[0..14]of longint;

procedure calc(n:int64;w:longint);
var i,j,k:longint;
    tmp:int64;
begin
  tmp:=n;
  fillchar(c,sizeof(c),0);
  while tmp<>0 do
   begin
     inc(c[0]);
     c[c[0]]:=tmp mod 10;
     tmp:=tmp div 10;
   end;
  for i:=c[0] downto 1 do
     if i=c[0] then
       for j:=c[i]-1 downto 1 do
        begin
         if i<>1 then
         for k:=0 to 9 do
           num[w][k]:=num[w][k]+(i-1)*shi[i-2];
         num[w][j]:=num[w][j]+shi[i-1];
        end
     else
       for j:=c[i]-1 downto 0 do
        begin
         if i<>1 then
         for k:=0 to 9 do
           num[w][k]:=num[w][k]+(i-1)*shi[i-2];
         num[w][j]:=num[w][j]+shi[i-1];
         for k:=c[0] downto i+1 do
           num[w][c[k]]:=num[w][c[k]]+shi[i-1];
        end;
  if (c[0]<>1)then for i:=c[0] downto 1 do inc(num[w][c[i]]);
  for i:=c[0]-1 downto 1 do
    for j:=0 to 9 do
      begin
        num[w][j]:=num[w][j]+i*shi[i-1];
        if i<>1 then num[w][j]:=num[w][j]-(i-1)*shi[i-2];
        if j=0 then num[w][j]:=num[w][j]-shi[i-1];
      end;
end;

procedure init;
var i:longint;
begin
  read(a,b);
  fillchar(num,sizeof(num),0);
  shi[0]:=1;
  for i:=1 to 12 do
   shi[i]:=shi[i-1]*10;
  calc(a-1,0);
  calc(b,1);
  for i:=0 to 8 do
   write(num[1][i]-num[0][i],' ');
  write(num[1][9]-num[0][9]); 
end;

begin
  init;
end.


  评论这张
 
阅读(67)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018