青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(2098) 評論(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
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲国产成人精品视频| 国产精品日韩高清| 最近中文字幕日韩精品 | 欧美激情亚洲自拍| 麻豆精品视频| 一本在线高清不卡dvd | 久久精品夜夜夜夜久久| 欧美一级在线播放| 国产在线观看一区| 欧美高清hd18日本| 欧美性一二三区| 久久黄金**| 欧美丰满少妇xxxbbb| 亚洲网友自拍| 欧美专区在线观看一区| 亚洲欧洲综合另类在线| aⅴ色国产欧美| 国内一区二区三区| 亚洲日韩成人| 国产欧美一区二区三区国产幕精品 | 久久综合给合| 亚洲特级片在线| 欧美一级专区免费大片| 日韩视频二区| 欧美一区二视频| 在线视频欧美日韩精品| 欧美亚洲一区三区| 亚洲午夜av| 久久久久国产成人精品亚洲午夜| 亚洲麻豆视频| 久久黄色网页| 亚洲欧美视频一区二区三区| 美国十次成人| 久久久久久久国产| 欧美午夜国产| 亚洲人久久久| 一区二区视频免费在线观看 | 欧美在线一区二区| 一区二区免费在线观看| 久久成人免费网| 亚洲免费视频成人| 欧美激情一区二区三区蜜桃视频| 久久久久一区| 国产欧美不卡| 亚洲视频大全| 亚洲性图久久| 欧美精品日韩综合在线| 欧美电影免费观看大全| 国产在线欧美日韩| 亚洲欧洲99久久| 亚洲欧美www| 国产精品二区二区三区| 亚洲精品乱码久久久久久久久| 国外成人性视频| 欧美一区二区三区在线免费观看| 午夜宅男欧美| 国产精品狠色婷| 这里只有精品在线播放| 亚洲午夜激情网页| 欧美私人网站| 亚洲无线视频| 欧美一级片久久久久久久| 欧美天堂亚洲电影院在线播放 | 久久精品91| 国产色视频一区| 欧美亚洲日本一区| 久久精品欧美日韩| 日韩一级片网址| 一区二区三区黄色| 国产精品成av人在线视午夜片| 99国产精品99久久久久久粉嫩| 亚洲伊人伊色伊影伊综合网 | 欧美成人69av| 亚洲级视频在线观看免费1级| 最新高清无码专区| 欧美日韩国产免费| 亚洲天堂网站在线观看视频| 香蕉尹人综合在线观看| 国产亚洲一级高清| 老司机精品福利视频| 亚洲国产91| 亚洲一区二区三区乱码aⅴ| 国产精品户外野外| 欧美一区视频| 亚洲第一区在线| 亚洲午夜小视频| 国产亚洲第一区| 免费视频一区二区三区在线观看| 亚洲欧洲精品一区二区| 亚洲欧美日韩精品久久久久| 国产亚洲精品一区二区| 欧美成人免费视频| 国产精品99久久久久久久女警| 久久不见久久见免费视频1| 亚洲电影在线| 国产精品va在线播放| 久久精品夜色噜噜亚洲a∨ | 欧美激情91| 亚洲影视九九影院在线观看| 国产一区三区三区| 欧美精品在线播放| 欧美主播一区二区三区美女 久久精品人 | 一区二区三区我不卡| 欧美日韩成人网| 欧美在线观看你懂的| 日韩一级大片在线| 欧美成黄导航| 久久国产主播精品| 一本大道久久精品懂色aⅴ| 国产一区二区三区不卡在线观看 | 欧美精品久久久久a| 先锋影音网一区二区| 最近中文字幕日韩精品| 久久久在线视频| 亚洲欧美日韩综合aⅴ视频| 91久久精品国产91性色| 国产在线精品自拍| 欧美视频免费在线观看| 欧美国产91| 久久男人av资源网站| 午夜视频一区| 亚洲综合色自拍一区| 亚洲久久一区| 欧美国产1区2区| 久久综合色天天久久综合图片| 亚洲欧美99| 亚洲性xxxx| 一区二区三区高清视频在线观看| 一区二区三区在线高清| 国产午夜一区二区三区| 欧美国产日本| 欧美xx69| 欧美国产日韩一区二区| 你懂的视频一区二区| 久久只精品国产| 久久噜噜亚洲综合| 欧美亚洲在线| 欧美在线亚洲综合一区| 欧美亚洲视频| 欧美一区精品| 久久爱www.| 久久夜色精品亚洲噜噜国产mv| 久久成人国产| 久久亚洲影院| 欧美成人精品不卡视频在线观看 | 午夜精品福利一区二区三区av | 亚洲第一色中文字幕| 一色屋精品视频在线观看网站| 国产在线精品二区| 在线观看日韩精品| 亚洲三级影院| 一区二区三区欧美激情| 亚洲一线二线三线久久久| 亚洲欧美国产制服动漫| 欧美一区三区三区高中清蜜桃 | 久久精品视频免费观看| 久久天堂成人| 亚洲第一视频| 中文无字幕一区二区三区| 午夜亚洲福利| 美乳少妇欧美精品| 欧美日韩精品福利| 国产欧美激情| 亚洲激情在线观看| 亚洲午夜在线观看| 久久影视三级福利片| 亚洲高清电影| 亚洲专区在线| 久久三级视频| 国产精品久久久久国产精品日日| 国产精品综合av一区二区国产馆| 韩国av一区二区三区在线观看| 亚洲精品欧美一区二区三区| 亚洲色无码播放| 久热精品视频在线| 夜夜嗨av一区二区三区四区| 欧美亚洲视频在线看网址| 欧美成人午夜| 国产日韩成人精品| 99精品99| 久久久久综合一区二区三区| 亚洲片国产一区一级在线观看| 亚洲一区二区三区免费观看 | 国产综合网站| 一区二区欧美视频| 久久亚洲欧美国产精品乐播| 日韩亚洲欧美成人| 久久综合亚州| 国产视频久久| 亚洲视频福利| 亚洲第一页中文字幕| 午夜精品久久久久久久久久久久久 | 欧美日韩国产区一| 永久555www成人免费| 午夜精品视频网站| 亚洲人成在线观看| 久久综合久久美利坚合众国| 国产精品专区h在线观看| 亚洲视频在线观看一区| 欧美高清日韩|