全国信息学奥林匹克联赛试题精解（2001-2003） (2009 年度畅销榜NO.1164 )

《中国计算机学会信息学奥林匹克系列丛书》由中国计算机学会信息学奥林匹克科学委员会主编，由全国著名专家学者精心编著而成。
本书收录了全国信息学奥林匹克联赛2001年至2003年的全部复赛试题，所有试题都给出了具体的算法分析和参考程序清单。对于其中一些试题，不仅给出了常用的基本算法，而且还提供了比较巧妙的优化算法，以开阔思路，启发思维。
本书深入浅出，可读性强，既适合教师辅导学生使用，也适合参加信息学奥林匹克联赛的学生自学，同时也是大专院校的计算机爱好者学习编程的优秀参考书。

第1章 2001年复赛试题解析
1.1 普及组
试题1 数的计数
试题2 最大公约数与最小公倍数问题
试题3 求前序排列
试题4 装箱问题
1.2 提高组
试题1 一元三次方程求解
试题2 数的划分
试题3 统计单词个数
试题4 CAR的旅行路线
第2章 2002年复赛试题解析
2.1 普及组
试题1 级数求和
试题2 选数
试题3 产生数
试题4 过河卒
2.2 提高组
试题1 均分纸牌
试题2 字符串变换
试题3 自由落体
试题4矩形覆盖
第3章 2003年复赛试题解析
3.1 普及组
试题1 乒乓球(table.bas/pas/c/c即)
试题2 数字游戏(galne.bas/pas/c/cpp)
试题3 栈(stack.bas/pas/c/叩p)
试题4 麦森数(MasOn.bas/pas/c/cpp)
3.2 提高组
试题1 神经网络(ne(work.bas/pas/c/cpp)
试题2 侦探推理(1ogic.bas/pas/c/cpp)
试题3 加分二叉树(tree.bas/pas/c/cpp)
试题4 传染病控制(印idemic.bas/pas/c/cpp)
附录A 拓扑排序
附录8 树的遍历

信息技术对人类社会的发展产生着深远的影响，已成为新世纪的一个标志。作为人类集体智慧的结晶，信息技术已成为一种时代文化。“计算机的普及要从娃娃抓起”成为“科教兴国”的一项重要内容。 一个国家、一个民族要立足于世界先进民族之林，关键在于拥有高素质的人才。综合国力的竞争，说到底是人才的竞争，培养和造就一大批优秀信息技术人才是当务之急。信息时代，信息技术已成为现代科学与技术的基础核心，成为人类的“通用智力工具”，在青少年中普及信息技术教育具有重要和深远的意义。 中国计算机学会从1984年起，就组织青少年参加信息学奥林匹克竞赛。二十余年，学会通过组织竞赛推动信息技术普及，促进青少年掌握信息技术知识，并提高他们的逻辑思维和解决问题的能力。为了培养和造就更多高素质的信息技术人才，中国计算机学会特别推出一套信息学奥林匹克系列指导丛书。这套丛书从基础知识开始，重点培养学生的创新思维方法和编程能力。本书的编著者大多是多年从事信息技术普及教学和信息学奥林匹克竞赛的指导者，有丰富的教学经验，他们编写的信息学奥林匹克系列丛书受到了全国青少年的喜爱，他们指导的学生曾多次在国际上获得金奖，为培养青少年的信息素养提供了很好的精神食粮。编著这套丛书的目的旨在培养学生逻辑思维、创新能力和全面提高青少年素质方面提供帮助。 该丛书的编写是开放式的，凡有志于向青少年普及信息技术的科技工作者和教育工作者都可以加入到这个行列中。

全国青少年信息学奥林匹克竞赛(National01ympiadinlnformatics，NOD是一项面向全国青少年的信息学竞赛和普及活动。NOI以及全国青少年信息学奥林匹克联赛(NOIP)等系列活动由中国科学技术协会主管，中国计算机学会主办，旨在向青少年普及计算机科学知识，为学校的信息技术教育提供动力和新的思路，给那些有才华的学生提供相互交流和学习的机会，通过竞赛和相关的活动培养和选拔优秀的计算机人才。 竞赛的目的是为了在更高层次上推动普及。受中国计算机学会的委托与指导，从1995年起江苏省青少年科技中心已连续多年成功承办了全国信息学奥林匹克联赛活动，数以十万计的青少年从中受益。联赛是全国性的比赛，是NOI的基础，遵循开放性原则，任何有条件和有兴趣的学校和个人，都可以在业余时间自愿参加，不和现行的学校教学相冲突，也不列入教学计划，是课外性质的因材施教活动。 在多年的联赛中，参与此项工作的老师与专家们积累了许多宝贵经验，他们曾经对1995年至2000年前六届联赛的普及组与提高组的全部初、复赛试题加以分析解答并编写成书，对活动的普及起到了很好的推动作用。现根据广大读者的要求，由中国计算机学会组织安排，这些专家与老师们又将第七届(2001年)至第九届(2003年)联赛的复赛试题予以剖析，汇集而成本收。本书共分为3章，每章分别对应于这几届全国联赛的普及组与提高组的复赛试题。本书紧密围绕联赛复赛大纲所涉及的知识点，以算法分析为主线，针对每一道试题都提供了问题描述，输入输出样例，问题分析，数据结构，参考程序清单和测试数据等几部分。通过分析这些试题，讲思想，讲方法，侧重基础知识训练，引导学生在实践中掌握科学的思维方法，提高应用计算机的能力。程序设计是一种创造性的劳动，因而在编写本书时，其指导思想侧重放在剖析思路与探讨思维方法方面，引导学生全面、灵活地把握解决问题的思路与方法，提高参赛选手的综合能力。 参加本书编写工作的有江苏省青少年信息学奥林匹克竞赛委员会(以下简称“奥赛委”)科学委员会的李立新教授、江苏省青少年信息学奥赛委普及委员会的高级教练章维铣、曹文老师以及中级教练员王静老师。全书由江苏省青少年信息学奥赛委科学委员会的王晓敏副主任策划并完成统稿，最后经李立新教授初审，清华大学计算机系教授、博士生导师、信息学奥林匹克竞赛中国队总教练吴文虎教授终审定稿。在成书的过程中，得到了中国计算机学会科学委员会诸多专家以及江苏省青少年信息学奥赛委科学委员会的宋方敏、沈军、朱玉珑等专家教授的指导，同时还得到江苏省青少年科技中心领导的大力支持，在此谨向他们表示感谢。 希望广大读者对本书提出宝贵的意见和建议，以便我们进一步修订，使之日臻完善。