您的位置:大榕树 \ 编程
|
Logo语言
|
Pascal语言
|
信息学奥赛
|
高考保送
| HTML版本
|
SGOI11之《黑白图像压缩》
http://www.mydrs.org 5/3/2002 大榕树
【题意简述】
输入一个十进制数串(长度不超过10000),代表一个长度不超过80000的01串(将0、1看做颜色号,0代表白,1代表黑),输出此01串的压缩形式。所谓压缩形式,是指将01串中连续片段(即连续成段的0或1)用一个字节(即一个不超过255的十进制数)表示,表示方法为:字节的最高位代表此片段的颜色是0还是1,低7位代表此片段的长度。输入保证所有连续的0或1片段的长度均小于128。 【初步分析】
这道题目题意比较清晰,难度并不大。初步设想是:读入十进制串,转换成二进制的01串,再按照题目要求的压缩方式处理每个连续片段后依次输出即可。
要将十进制串转换成二进制串,只需依次将十进制串中的每个数转换成二进制即可。十进制转换成二进制,可以用短除法,是比较简单的。
压缩连续片段的方法也很简单,只需从前向后扫描01串,统计每个连续片段,对于每个连续片段,输出其颜色(0或1)乘以最高位的位权 (=128)加上它的长度(<128)的值即可。
一点需要主意的是,本题输入的长度是指01串,最大为80000,因此要用Longint存,如果看题不仔细,认为最大长度为10000而误用了Integer,则会引起严重问题。
这样看来,此题还是不难的,然而还有一些东西值得推敲。 【精益求精】
注意到,本题的规模还是比较大的,最多涉及到10000个十进制数和80000个0或1,如果我们采用读入--转换--保存--处理输出的方式,至少要存80000个0或1的信息,无法在Turbo Pascal的静态内存中保存。所以,我们有必要用"边读边做"的方式。
首先,我们保存到目前为止的"上一个"连续片段的颜色号和长度。那么,每读入一个十进制数,我们就将其转换为二进制串,并把结果(八位而已)存在一个临时数组里,再从前向后扫描处理每一位。处理方法是:如果当前处理位的颜色与"上一个"片段的颜色相同,则将记录的长度加1;否则,说明"上一个"片段结束,就按照前面说的方法输出"上一个"片段,同时,新的"上一个"片段开始,颜色同当前位,长度为1。
用这个方法要注意第一个和最后一个连续片段的处理。首先,必须特殊处理第一个十进制数,读入后,将它的第一位颜色记为"上一个"连续段的颜色,初始化"上一个"连续段的长度为1,然后处理它的剩下七位。第一个十进制数处理后,就可以用上面的方法依次读入、转换、处理剩下的所有数。最后,不要忘了在处理完最后一个十进制数的最后一位之后,再输出记录的最后一个"上一个"片段。
这样,就可以比较方便地完成此题。 【总结】
这是一道简单的题目,要做什么,怎样做,基本上可以直接从题意得到,所以,算法上我们无需做太多的分析和考虑。
得出初步算法后,我们发现本题用"边读边做"的方法比较好,所以用了这种技巧。随之而来的就是一些特殊情况的处理,对于这些细节上的问题,只要缜密分析,冷静思考,考虑周全各种情况,就能够有条有理地解决它们。
本题是一道基础题,难度不大。然而基础题有基础题的价值,它不仅可以考查选手的基础是否牢固,而且能充分检验选手是否细心,思考问题是否周密,解题思路是否清晰。因此,这种题目还是值得一做的。 【程序】
见AHO2T3.pas。
|
□-
近期热门文章 |
□-
相关文章 |
1.
NOIP2006竞赛大纲
[8307]
2.
七类高中生具有保送资格
[5911]
3.
NOI2006获奖选手名单
[4956]
4.
关于举办NOIP2006模拟赛的通告
[4107]
5.
Turbo Pascal各语句运行速...
[3595]
6.
Turbo王者归来新Delphi免费...
[3182]
7.
IOI2006我国4名选手全部获得金...
[2946]
8.
关于APIO2007与IOI2007...
[2764]
9.
noip倒计时 by 枯叶蝴蝶
[2684]
10.
朱泽园:思想上的金牌更重要
[2169]
|
|