大榕树——让我们共成长!
大榕树 myDrs.org
您的位置:大榕树 \ 编程       |  Logo语言   |  Pascal语言   |  信息学奥赛   |  高考保送    |  HTML版本
|  信息学奥赛>>解题报告>>SGOI11之《黑白图像压缩》         本站全文搜索: 友情提示:

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

来 源:ChinaSchool
共有2413位读者阅读过此文

  • 上篇文章SGOI11之《Kitty猫基因编码》
  • 下篇文章SGOI11之《芝麻开门》

  • 发送邮件
    保存页面 打印文章 HTML版本 发表评论

    □- 近期热门文章 □- 相关文章
    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]
    SGOI第14次友谊赛成绩
    SGOI-14友谊赛测试数据
    SGOI14友谊赛试题
    SGOI第十三次友谊赛数据
    SGOI第13次友谊赛成绩揭晓
    SGOI第十三次友谊赛试题
    SGOI第13次友谊赛竞赛规则
    Sgoi12之《黑白瓷砖》
    《哈利·波特与魔法石》
    Sgoi12之《网络传输》
     

    关于本站 | 合作伙伴 | 联系方式
    大榕树 版权所有 ©1999-2006 www.myDrs.org 闽ICP备05000721号