• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            PKU2282 The Counting Problem

            Posted on 2007-02-20 15:49 oyjpart 閱讀(2091) 評論(5)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
            看看你的心有多細?

            The Counting Problem
            Time Limit:3000MS? Memory Limit:65536K
            Total Submit:741 Accepted:368

            Description
            Given two integers a and b, we write the numbers between a and b, inclusive, in a list. Your task is to calculate the number of occurrences of each digit. For example, if a = 1024 and b = 1032, the list will be

            1024 1025 1026 1027 1028 1029 1030 1031 1032

            there are ten 0's in the list, ten 1's, seven 2's, three 3's, and etc.

            Input
            The input consists of up to 500 lines. Each line contains two numbers a and b where 0 < a, b < 100000000. The input is terminated by a line `0 0', which is not considered as part of the input.

            Output
            For each pair of input, output a line containing ten numbers separated by single spaces. The first number is the number of occurrences of the digit 0, the second is the number of occurrences of the digit 1, etc.

            Sample Input

            1 10
            44 497
            346 542
            1199 1748
            1496 1403
            1004 503
            1714 190
            1317 854
            1976 494
            1001 1960
            0 0
            

            Sample Output

            1 2 1 1 1 1 1 1 1 1
            85 185 185 185 190 96 96 96 95 93
            40 40 40 93 136 82 40 40 40 40
            115 666 215 215 214 205 205 154 105 106
            16 113 19 20 114 20 20 19 19 16
            107 105 100 101 101 197 200 200 200 200
            413 1133 503 503 503 502 502 417 402 412
            196 512 186 104 87 93 97 97 142 196
            398 1375 398 398 405 499 499 495 488 471
            294 1256 296 296 296 296 287 286 286 247
            

            Source
            Shanghai 2004

            我采用的是每一位統計每一個數字的方法
            我的想法就是 某一位出現某個數字的次數 就是其他位可能出現的數字的總和
            比如1134 第二位出現1就應該是前面的1+后面的34+1(還有00呢) 故是135種
            下面我列出了我的草稿:
            (0代表是0的情況 <代表小于本位數字 =代表等于本位數字 >代表大于本位數字)
            (post代表后面形成的數字 pre代表前面形成的數字)
            第一位
            0: 0
            <:本位權
            =:?? pre+1
            >:? 0
            第K位
            0:??? pre*本位權
            <:?? (pre+1)*本位權
            =:?? pre*本位權+post+1
            >:? pre*本位權
            最后一位
            0 || <= : pre+1
            > :??????? pre
            注意 如果數字只有1位 則不能應用第一位規則 而應該應用最后一位規則
            我WA了一次這里

            Solution
            //by oyjpArt

            ?

            ?1#include?<stdio.h>
            ?2#include?<math.h>
            ?3#include?<memory.h>
            ?4
            ?5const?int?N?=?10;
            ?6int?w[N],?d[N],?num1[N],?num2[N],?nd;?//??è¨,êy×?,3???′?êy????1,????2,??êy
            ?7
            ?8inline?int?pre(int?pos)?{
            ?9????int?tot?=?0,?i,?base;
            10????for(base?=?1,?i?=?pos-1;?i>=0;?i--)?{
            11????????tot?+=?d[i]*base;
            12????????base?*=?10;
            13????}

            14????return?tot;
            15}

            16
            17inline?int?post(int?pos)?{
            18????int?tot?=?0,?i,?base;
            19????for(base?=?1,?i?=?nd-1;?i>pos;?i--)?{
            20????????tot?+=?d[i]*base;
            21????????base?*=?10;
            22????}

            23????return?tot;
            24}

            25
            26void?cal(int?x,?int?num[])?{
            27????int?base?=?1,?i,?j,?tmp?=?x;
            28????nd?=?(int)ceil(log10(x+1));?//??????êy
            29????if(nd?==?0)?++nd;
            30????for(i?=?nd-1;?i>=0;?i--)?{?//??????ò???μ?è¨?μ?2¢·?à?3???ò???êy
            31????????w[i]?=?base;
            32????????base?*=?10;
            33????????d[i]?=?tmp%10;
            34????????tmp?/=?10;
            35????}

            36????for(i?=?0;?i<nd;?i++)?{?//??óúμúi??
            37????????if(i?==?0?&&?nd?!=?1)??//μúò???ì?êa′|àí?
            38????????????for(j?=?0;?j<=9;?j++)?{?//í3??êy×?j?úi??3???μ?′?êy???í?
            39????????????????if(j?!=?0?&&?j?<?d[i])????????num[j]?+=?w[i];?//±???è¨
            40????????????????else?if(j?==?d[i])????num[j]?+=?post(i)+1;?//′ói+1?aê?D?3éμ?êy×?+1
            41????????????}

            42
            43????????else?if(i?==?nd-1)??//×?oóò???ì?êa′|àí
            44????????????for(j?=?0;?j<=9;?j++)?{
            45????????????????if(j?<=?d[i])???????num[j]?+=?pre(i)+1;?//i?°??D?3éμ?êy×?+1
            46????????????????else????????????????num[j]?+=?pre(i);
            47????????????}

            48
            49????????else????????????//ò?°??é??
            50????????????for(j?=?0;?j<=9;?j++)?{?
            51????????????????if(j?==?0)?{
            52????????????????????if(d[i]?==?0)???num[j]?+=?(pre(i)-1)*w[i]?+?post(i)+1;
            53????????????????????else????????????num[j]?+=?pre(i)*w[i];
            54????????????????}

            55????????????????else?if(j?<?d[i])???num[j]?+=?(pre(i)+1)*w[i];
            56????????????????else?if(j?==?d[i])??num[j]?+=?pre(i)*w[i]?+?post(i)+1;
            57????????????????else????????????????num[j]?+=?pre(i)*w[i];
            58????????????}

            59????}

            60}

            61
            62int?main()?{
            63????int?a,?b,?t,?i;
            64????while(scanf("%d%d",?&a,?&b),?a+b)?{
            65????????memset(num1,?0,?sizeof(num1));
            66????????memset(num2,?0,?sizeof(num2));
            67????????if(a?>?b)?{
            68????????????t?=?a;
            69????????????a?=?b;
            70????????????b?=?t;
            71????????}

            72????????if(a?>?0)?cal(a-1,?num1);
            73????????cal(b,?num2);
            74????????printf("%d",?num2[0]-num1[0]);
            75????????for(i?=?1;?i<10;?i++)
            76????????????printf("?%d",?num2[i]-num1[i]);
            77????????putchar('\n');
            78????}

            79????return?0;
            80}

            81
            這個注釋不知道怎么拷出來就變成亂碼了 請高手指點

            Feedback

            # re: PKU2282 The Counting Problem   回復  更多評論   

            2007-02-20 16:24 by 萬連文
            不知道pku是什么意思???

            # re: PKU2282 The Counting Problem   回復  更多評論   

            2007-02-20 21:20 by oyjpart
            Peking University
            Here we imply Peking University ACM Online Judge

            # re: PKU2282 The Counting Problem   回復  更多評論   

            2007-02-24 16:31 by sheep
            這里是utf8的,大概你輸入的是gb2312所以就亂馬了

            # re: PKU2282 The Counting Problem   回復  更多評論   

            2007-02-26 21:46 by asp.j
            是ANSI吧?

            # re: PKU2282 The Counting Problem   回復  更多評論   

            2010-06-03 02:04 by Jackal
            第一位等于的情況應該是第一位post+1,不是pre+1
            狠狠色婷婷久久综合频道日韩| 久久夜色精品国产欧美乱| 91精品国产91久久久久福利| 99久久成人国产精品免费| 97久久精品人人澡人人爽| 一极黄色视频久久网站| 97超级碰碰碰久久久久| 色偷偷91久久综合噜噜噜噜| 色欲av伊人久久大香线蕉影院| 亚洲国产成人久久精品影视| 欧美激情一区二区久久久| 国内精品久久国产大陆| 无码人妻久久一区二区三区蜜桃| 久久精品一本到99热免费| 久久久WWW成人免费毛片| 久久国产免费观看精品3| 亚洲欧美一级久久精品| 香蕉久久一区二区不卡无毒影院| 国内精品九九久久精品| 久久强奷乱码老熟女| 国产激情久久久久影院小草| 日韩人妻无码精品久久免费一| 日韩一区二区三区视频久久| 伊人久久综在合线亚洲2019| 久久综合九色综合网站| 中文字幕乱码久久午夜| 亚洲国产精品成人AV无码久久综合影院 | 久久精品国产一区二区三区日韩| 无码国内精品久久人妻麻豆按摩| 国产99久久精品一区二区| 麻豆一区二区99久久久久| 女人高潮久久久叫人喷水| 伊人久久成人成综合网222| 久久久久无码专区亚洲av| 一本久久久久久久| 国产福利电影一区二区三区久久久久成人精品综合 | 久久婷婷五月综合国产尤物app | 亚洲午夜精品久久久久久app| 国产精品成人精品久久久| 成人国内精品久久久久影院VR| 国产精品99久久99久久久|