• <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香蕉| 日韩欧美亚洲综合久久影院Ds| 伊人久久大香线蕉综合热线| 欧美一区二区三区久久综| 99精品久久久久久久婷婷| 久久亚洲国产精品成人AV秋霞| 亚洲伊人久久精品影院| 国产精品熟女福利久久AV| 久久精品国产亚洲av麻豆蜜芽| 久久se精品一区精品二区| 久久婷婷是五月综合色狠狠| 久久这里只有精品首页| 伊人色综合久久天天人手人婷 | 久久se精品一区精品二区| 亚洲国产精品无码久久青草 | 久久精品国产2020| 91精品久久久久久无码| 久久久久久夜精品精品免费啦| 精品久久人人做人人爽综合| 久久天天躁狠狠躁夜夜avapp| 蜜臀久久99精品久久久久久 | 欧美粉嫩小泬久久久久久久| 精品一区二区久久| 亚洲国产精品无码成人片久久| 久久成人国产精品一区二区| 99久久久精品| 漂亮人妻被黑人久久精品| 久久WWW免费人成一看片| 伊人情人综合成人久久网小说| 久久人人爽人人爽人人片AV东京热| 国产亚洲欧美成人久久片 | 999久久久免费国产精品播放| 久久国产免费观看精品3| 久久精品国产99久久久古代| 久久婷婷人人澡人人爽人人爱| 久久久久久国产a免费观看黄色大片| 久久人人爽人人爽AV片| 久久久久亚洲AV成人网人人网站 | 区久久AAA片69亚洲|