全国信息学奥林匹克联赛试题精解（2001-2003）

    书籍
    计算机书籍
《中国计算机学会信息学奥林匹克系列丛书》由中国计算机学会信息学奥林匹克科学委员会主编，由全国著名专家学者精心编著而成。
本书收录了全国信息学奥林匹克联赛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 均分纸牌

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