• <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
            亚洲国产精品久久久久婷婷软件| 久久无码国产| 久久精品国产亚洲AV无码麻豆 | 香蕉久久夜色精品国产小说| 亚洲国产精品久久久久网站| 国产高潮国产高潮久久久91| 偷偷做久久久久网站| 国产成人久久激情91| 欧美麻豆久久久久久中文| 久久精品亚洲中文字幕无码麻豆| 国产精品免费久久| 粉嫩小泬无遮挡久久久久久| 中文字幕精品无码久久久久久3D日动漫| 久久AV高清无码| 久久久久久久女国产乱让韩| 国产精久久一区二区三区| 一本一道久久综合狠狠老 | 99久久国产综合精品网成人影院| 久久无码中文字幕东京热| 国产激情久久久久影院老熟女| 久久久久久国产精品无码超碰| 久久亚洲精品无码播放| 久久er国产精品免费观看8| 久久人爽人人爽人人片AV| 综合久久精品色| 久久久久18| 久久天天躁狠狠躁夜夜2020| 香港aa三级久久三级| 人人狠狠综合久久亚洲婷婷| 久久综合综合久久综合| 久久久久久精品成人免费图片 | 国产精品视频久久久| 亚洲AV日韩精品久久久久久| 伊人久久大香线蕉精品不卡| 久久一区二区免费播放| 香蕉aa三级久久毛片| 亚洲人成网站999久久久综合| 久久久久免费视频| 伊人久久一区二区三区无码| 青青热久久国产久精品| 久久无码中文字幕东京热|