搜索
1ACM/ICPC实验指导2前言ACM的全称是AssociationforComputingMachinery（美国计算机学会），建立于1947年，是世界上第一个计算机教育和科研的组织，也是最有影响的计算机组织。如今，ACM已经有超过8万个成员，主要活动包括一些专题的兴趣小组与一系列高水平的学术会议，还有一些面向不同层次的学术竞赛，ACM/ICPC就是其中之一。ACM/ICPC（ACMInternationalCollegiateProgrammingContest），即ACM国际大学生程序设计竞赛，是由ACM提供给大学生的一个展示和提高解题与编程能力的机会。赛事由各大洲区域预赛和全球总决赛两个阶段组成。各预赛区第一名自动获得参加全球总决赛的资格。决赛安排在每年的3-4月举行，而区域预赛一般安排在上一年的9-12月举行。一个大学可以有多支队伍参加区域预赛，但只能有一支队伍参加全球总决赛。决赛的颁奖仪式将和计算机界权威的学术奖——图灵奖的颁奖仪式同时进行。全球总决赛第一名将获得奖杯一座。另外，成绩靠前的参赛队伍也将获得金、银和铜牌。而解题数在中等以下的队伍会得到确认但不会进行排名。ACM/ICPC竞赛的历史可以上溯到1970年，当时在美国德克萨斯A&M大学举办了首届比赛。作为一种全新的发现和培养计算机科学顶尖学生的方式，竞赛很快得到美国和加拿大各大学的积极响应。1977年，在ACM计算机科学会议期间举办了首次总决赛，并演变成为目前的一年一届的多国参与的国际性比赛。最初几届比赛的参赛队伍主要来自美国和加拿大，后来逐渐发展成为一项世界范围内的竞赛。特别是1997年IBM开始赞助赛事之后，赛事规模增长迅速。在赛事的早期，冠军多为美国和加拿大的大学获得。而进入1990年代后期以来，俄罗斯和其它一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代表队则在2002年美国夏威夷第26届和2005年上海举行的第29届全球总决赛上两夺冠军。ACM/ICPC竞赛既是一项重大的国际赛事，又是一个优秀的训练学生编程能力的平台。学生在准备ACM/ICPC竞赛时，可以巩固编程语言、数据结构、算法等程序设计所需的基础知识，提高编写程序的熟练程度，还可以积累程序调试的经验，为计算机科学的进一步学习和研究打下良好的基础。作者总结了多年ACM/ICPC竞赛的教练经验，认为ACM/ICPC竞赛所需要的基础知识与能力包括：程序设计语言基本功、数据结构的基础知识、相关的数学知识与良好的团队精神。首先，在ACM/ICPC的道路上，语言都是大家过的第一道关。熟练掌握一门编程语言，就可以在实际比赛中大大提高效率，节约时间，将更多的时间用于分析题目，寻求解题方法，而不是纠缠于语言细节。其次，数据结构与算法是真正的核心，也是本书的重点。掌握基本的队列、堆栈和图的基本表达与操作与熟练掌握语言的语法知识一样，是每一个ACM/ICPC选手必需的技能。线段树、并查集等高级数据结构在竞赛中也经常出现，因此也需要熟练掌握。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。常用算法中的另一类是以“相似或相同子问题”为核心的，包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划，如何抽象出重复的子问题是很多题目的难点所在。第三，在ACM/ICPC竞赛中，很多题目可以通过数学方法进行分析，从而找到最为简介的解决方案。竞赛所需要的数学知识主要包括：①离散数学：作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。②数论：数论中定理颇多，因此知识点较为零散。但掌握了数论的分析方法，某些难题也可以迎刃而解。③计算几何：计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点3很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。④线性代数：对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。第四，ACM/ICPC竞赛形式为三人构成的小组，在竞赛过程中，除了对个人的知识、智力等方面的挑战之外，也是对三个人之间的团队精神的考验。在竞赛过程中要避免各自为战的情况。在训练的过程中，组员之间就应当有明确的分工并积极交流。最后，ACM/ICPC竞赛毕竟是以代码取胜的竞赛，无论有多少理论知识的储备，在赛场上拼的都是熟练度，这就需要在训练过程中做到练习，练习，再练习。只有通过对具体题目的分析，才能够体会到ACM/ICPC竞赛的解题思路，提高自身编写代码、调试程序的能力，积累和总结编程技巧，加强团队合作。只有以强大的练习作为支撑，才能够在赛场上做到胸有成竹。本书在第一章中简要回顾了C语言的语法，并针对ACM/ICPC竞赛中可能出现的问题举例进行详细讲解。第二章主要讲解了数据结构的基础知识并给出几种简单常见的数据结构：线性表、栈、队列、树。第三章到第九章均为习题章节，按照ACM/ICPC竞赛中常见的题目分类形式分为模拟题、搜索题、图论题、动态规划题、数论与组合数学题、计算几何题、高级数据结构题。其中给出了各类题目的例题，解题思路与标程，并给出大量习题供选手练习。本书中的例题与习题大多来自各区域选拔赛(Regional)、地区赛(Local)、信息学竞赛、USACO、POJMonthly等竞赛或平台，在此感谢各竞赛主办方提供竞赛题目与调试数据的下载。在本书编写过程中，大连理工大学2008级集训队的同学给贡献了很多资料与源代码，特此表示感谢。4目录前言..............................................................................................................................................2目录..............................................................................................................................................4第一章C语言基础知识..................................................................................................................81.1数据类型............................................................................................................................81.2表达式................................................................................................................................91.3分支语句..........................................................................................................................101.4循环语句..........................................................................................................................121.5函数..................................................................................................................................141.6格式化输入输出..............................................................................................................15第二章数据结构基础知识...........................................................................................................172.1线性表：...........................................................................................................................172.2栈.......................................................................................................................................202.3队列...................................................................................................................................222.4排序...................................................................................................................................262.5树.......................................................................................................................................36第三章模拟题...............................................................................................................................41理论基础及简介：.................................................................................................................41例题1：约瑟夫问题..............................................................................................................41例题2：排列问题..................................................................................................................43例题3：SortingbySwapping................................................................................................45习题...................................