信息学奥林匹克竞赛指导——2002竞赛试题解析 (2010 年度畅销榜NO.3728 )

本书收集了2002年国际、国内有关信息学奥林匹克竞赛试题，重点在于分析解题思路和方法上，其中包括数学模型的构建、相应的算法分析以及程序的编写等，这些试题有相当的难度，是训练思维、提高解题技巧的很好参考资料。
书中对试题类型进行了归纳，增强了本书的可读性，既便于教师对参赛学生的辅导，又便于学生自学，所以本书既是参赛选手的必读书，也可作为理工科院校编程爱好者提高分析问题、解决问题能力的参考书。

第1章 与课本知识相关的例题
1.1 级数求和
1.2 自由落体

第2章 数据结构类的例题
2.1 有关字符串处理的例题
2.2 并查集与路径压缩

第3章 数论类的例题
3.1 荒岛野人

第4章 组合分析类的例题
4.1 机器人m号

第5章 计算几何学类的例题
5.1 矩形覆盖

第6章 图论类的例题
6.1 玩具兵

第7章 搜索策略类的例题
7.1 枚举法
7.2 回溯法

第8章 动态程序设计方法类的例题
8.1 过河卒
8.2 工作安排
8.3 烦人的青蛙
8.4 颁奖典礼
8.5 贪吃的九头龙

第9章 模拟策略类的例题
9.1 灭鼠行动
9.2 调皮的小孩
9.3 两支竿

第10章 “贪心法”类的例题
10.1 均分纸牌
10.2 月亮森林

第11章 “构造法”类的例题
11.1 乌托邦
11.2 XOR压缩
11.3 贝奇方块
11.4 新俄罗斯方块

信息科学与技术正在对人类社会的发展产生难以估量的深远影响，已经成为新世纪的一个标志。作为人类总体智慧的结晶，电脑已经成为一种新的现代文化。“计算机的普及要从娃娃抓起”已经成为“科教兴国”的一项重要内容。 一个国家、一个民族要想不落伍，要想跻身于世界先进民族之林，关键在于拥有高素质的人才；综合国力的竞争，说到底也是人才的竞争。电子计算机是现代科学与技术的基础和核心，它的飞速发展，把社会生产力水平提到前所未有的高度，人类进入了信息时代。电脑对人类社会的发展所起的巨大作用，特别是对人类智能的发展所起的促进作用，已为人们普遍认识。计算跟语言一样是人类社会每时每刻都不可缺少的。现在，人类已经拥有了帮助自己进行复杂计算与思维的工具，电子计算机起到了人脑延伸的作用。以往历史上的技术革命，只能起到创造和改进工具，用机器代替人的体力的作用；而计算机则是把人从重复性的或有固定程式的脑力劳动中解放出来，使自己的智能获得空前的发展。作为“人类通用智力工具”的计算机在开发人类智能方面所起的无与伦比的作用不容忽视。信息技术是以计算机为龙头的。这也就是信息技术与基础教育相结合，能够成为当今世界的大趋势的一个原因。从信息社会要求人才具备的科学素养看，数学、物理学、化学、生命科学和信息科学是五大支柱，这正是联合国教科文组织倡导举行五项国际学科奥林匹克竞赛的内容。 国际信息学奥林匹克(International Olympiad in Informatics，IOI)始于1989年，到2003年已成功地举办了15届。这是一种智力与应用计算机能力的大赛。从益智的角度看，是用电脑帮助开发人脑，重在提高思维能力，培养创新意识。在中国队的训练中强调德智体美全面发展；心态上自立、自尊、自信、自强，要怀着中华民族的自豪感和自信心去参赛；这种心态是学习、训练和取胜的重要条件。15届比赛，中国队每届都取得了名列前茅的好成绩，59人次参赛，夺得59块奖牌，其中金牌30块、银牌17块、铜牌12块。特别是IOI'95(荷兰)突破了前6届比赛女孩与金奖无缘的纪录，两名中国女选手荣登金牌领奖台。在IOI'96(匈牙利)上中国队又实现了全金的突破，四名选手，每人获得一块金牌。 从大局看，竞赛不是目的，是推动普及的手段，我们的目的只有一个：科教兴国。竞赛活动带有因材施教、因材施测的特点。普及是有层次的，与学科竞赛有关的普及活动，对青少年而言属于比较高的层次，当然就有相当的难度。我们编写的这套竞赛指导丛书，涉及程序设计语言、常用算法、组合数学、图论、人工智能搜索等的基本知识和基本方法。这些理论知识往往都是通过竞赛当中的一些实例来讲解的，重点放在解题思路上，书中有许多题目比较新颖，很难去套固定算法或固定模式，这中间有些招数是选手们想出来的。从中可以看出信息学奥林匹克要求创新，鼓励创新。当然，书中给出的解法，对青少年读者而言，我们希望仅仅起到抛砖引玉的作用，并且热切盼望引出更多的“玉”来。作为老师，我和王建德都这样想，“精心育桃李，热望青胜蓝”就是我们编写这套丛书的初衷。