编审委员会

顾问: 李澎林潘海涵

主任: 张聚

副主任: 宋国琴蔡铁峰赵端阳朱新芬

编委: (按姓氏笔画为序)

王洁王荃冯志林成杏梅

刘均刘文程刘勤贤吕圣军

杜丰杜树旺吴艳何文秀

应亚萍张建奇陈伟杰郑利君

宗晓晓赵建锋郝平金海溶

姚晶晶徐欧官郭伟青曹平

曹祁傅永峰鲍卫兵潘建电子信息技术和计算机软件等技术的快速发展，深刻地影响着人们的生产、生活、学习和思想观念。当前，以工业4.0、两化深度融合、智能制造和“互联网+”为代表的新一代产业和技术革命，把信息时代的发展推到一个对于国家经济和社会发展影响更为深远的新阶段。

在新的产业和技术革命的背景下，社会对高校人才的培养模式、教学改革以及高校的转型发展都提出了新的要求。2015年，浙江省启动应用型高校示范学校建设。通过面向应用型高校的转型建设增强学生的就业创业和实践能力，提高学校服务区域经济社会发展和创新驱动发展的能力。通过坚持“面向需求、产教融合、开放办学、共同发展”的高校发展理念，围绕一流的应用型大学建设和一流的应用型人才培养目标，我们做了一系列的探索和实践，取得了明显实效。

作为应用型高校转型建设的重要举措之一和应用型人才培养的主要载体，本套规划教材着眼于应用型、工程型人才的培养和实践能力的提高，是在应用型高校建设中一系列人才培养工作的探索和实践的总结和提炼。在学校和学院领导的直接指导和关怀下，编委会依据社会对电子信息和计算机学科人才素质和能力的需求，充分汲取国内外相关教材的优势和特点，组织具有丰富教学与实践经验的双师型高校教师成立编委会，编写了这套教材。

本套系列教材具有以下几个特点: 

(1) 教材具有创新性。本系列教材内容体现了基本技术和近年来的新技术，注重技术方法、仿真例子和实际应用案例的结合。

(2) 教材注重应用性。避免复杂的理论推导，通俗易懂，便于学习、参考和应用。注重理论和实践的结合，加强应用型知识的讲解。(3) 教材具有示范性。教材中体现的应用型教学理念、知识体系和实施方案，在电子信息类和计算机类人才的培养以及应用型高校相关专业人才的培养中具有广泛的辐射性和示范性。

(4) 教材具有多样性。本系列教材既包括基本理论和技术方法的课程，也包括相应的实验和技能课程，以及大型综合实践性学科竞赛方面的课程。注重课程之间的交叉和衔接，从不同角度培养学生的应用和实践能力。

(5) 本套教材的编著者具有丰富的教学和实践经验。他们大多是从事一线教学和指导的、具有丰富经验的双师型高校教师。他们多年的教学心得为本教材的高质量出版提供了有力保障。

本套系列教材的出版得到浙江省教育厅相关部门、浙江工业大学教务处和之江学院领导以及清华大学出版社的大力支持和广大骨干教师的积极参与，得到学校教学改革和重点教材建设项目的资助，在此一并表示衷心的感谢。

希望本套教材的出版能够在转变教学思想，推动教学改革，更新知识体系，增强学生实践能力，培养应用型人才等方面发挥重要作用，并且为应用型高校的转型建设提供课程支撑。由于电子信息技术和计算机技术的发展日新月异，以及各方面条件的限制，本套教材难免存在不足之处，敬请专家和广大师生批评指正。

高等学校计算机类创新与应用型规划教材编审委员会

2016年10月ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest, ACM/ICPC)由国际计算机界历史悠久、颇具权威性的组织ACM(Association for Computing Machinery,美国计算机协会)主办,是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,旨在使大学生运用计算机充分展示自己分析问题和解决问题的能力。1970年,美国德克萨斯A&M大学举办了首次区域竞赛,从而拉开了国际大学生程序设计竞赛的序幕。1977年,在ACM计算机科学会议期间举办了首次总决赛,并演变成为一年一届的多国参与的国际性比赛。因历届竞赛都荟萃了世界各大洲的精英,云集了计算机界的“希望之星”,而受到国际知名大学的重视,并受到全世界众多著名计算机公司的高度关注,成为世界各国大学生最具影响力的国际级计算机类的赛事。

此项赛事的主办目的不单是培养参赛选手的创造力、团队合作精神以及他们在软件程序开发过程中的创新意识,同时也是检测选手们在压力下进行开发活动的能力。因此,ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台,是大学计算机教育成果的直接体现,是信息企业与世界顶尖计算机人才对话的最好机会。

ACM国际大学生程序设计竞赛1996年进入中国,上海交通大学作为我国内地高校最早的参赛队之一,曾７次进军总决赛,并于2002年将ACM金杯首次带到亚洲,打破了几十年来欧美国家对这一赛事的绝对统治地位,更震惊了世界。

2005年4月6日,在上海举办的“第29届ACM国际大学生程序设计竞赛”总决赛中,上海交通大学团队成功解答8道题,以一题的领先优势力克来自世界六大洲29个国家和地区的78支参赛队,捧获“世界上最聪明的人”的冠军奖杯。时隔3年,ACM全球总决赛冠军奖杯再次回到上海交通大学。2018年4月,ACMICPC在北京举行,由北京大学承办,而北京大学在最后时刻完成G题夺得金牌。

国际ACM比赛是世界上规模最大、历史最长、影响最深的全球性计算机专业竞赛,它要求每一名队员不仅具有扎实的数学功底、非凡的算法设计能力、娴熟的编程技巧,而且具备很好的协作精神、稳定的心理素质和快速的临场应变能力。

为了帮助各个大专院校的大学生们了解国际大学生程序设计竞赛,了解其程序设计的方法,提高参与校级、省级和亚洲区国际大学生程序设计竞赛的兴趣,特编写本书。

全书共12章。

第1章: 基础编程技巧题。主要是比较容易的题目,也称简单题,尤其适合刚开始熟悉ACM大学生程序设计竞赛题的同学。通过这些题目的练习,熟悉数据的输入、输出格式,基本编程方法,在线提交系统的使用,常见错误及其对策。

第2章: 模拟编程技巧题。根据题目的要求逐步实现目标,虽然没有经典的算法可以使用,正确理解题目是关键的要素。例如,题目Parencodings等。

第3章: 字符串处理技巧题。主要是字符串的处理,这也是考察参赛者细心的一类题目,需要对各种情况进行仔细分析,如题目A WellFormed Problem等。

第4章: 大整数运算技巧题,如题目Martian Addition、Reciprocals等。

第5章: 基本数据结构题,如题目Trees Made to Order等。

第6章: 搜索算法题。通常有深度优先搜索算法和广度优先搜索算法,如The Game等。

第7章: 动态规划算法题。这些题目使用动态规划算法,会使运行时间较短、效率较高,如题目City Game和How Many Ways等。

第8章: 贪心算法题。使用贪心算法的题目,如题目Highway和Warfare等。

第9章: 回溯算法题。使用回溯算法的题目,如题目Anagrams by Stack等。

第10章: 图论算法题。主要包含拓扑排序、Floyd算法和二分图等,如Street Directions等。

第11章: 几何题。主要是几何计算题目,如题目Farmland等。

第12章: 数学题。主要是数学计算题目,如题目Smith Numbers等。

本部分通过大量实例介绍了竞赛中常用的算法,并对如何灵活应用这些算法进行了比较详细的分析和深入浅出的讲解。

本书所用的语言是C/C++,并在MinGW Developer Studio或Code Blocks编译器中调试通过。在运行时间和内存占用的性能方面,C++并不比C语言优越,只是C++有丰富的模板库函数,输入/输出语句简单,编写的代码看起来格式更工整而已。在有大量输入/输出数据的题目中,书中会特别提醒读者需要使用C语言的输入/输出。

显然,Accepted是我们的目标,算法是我们不断探索的道路,好的算法让我们容易达到目标。本书中的算法,虽然作者经过反复斟酌,不断优化和简化,但仍然不敢认为是最优的。因为对算法的探索,正如金庸笔下的大侠们苦练武功一样,是没有止境的。

本书中虽然描述的是ACM国际大学生程序设计竞赛中最基本的算法,但它也已经超出了一般本科教科书讲授的范围。清华大学计算机科学与技术系博士生导师、国际信息学奥林匹克中国队总教练吴文虎教授认为,算法的确是艺术,“艺术与科学是相通的,都会给人以美的享受。”①希望读者能从本书中体会到这一点。

本书可以作为高等院校有关专业的本科和大专学生参加国际大学生程序设计竞赛的辅导教材,或者作为高等院校数据结构、C/C++程序设计或算法设计与分析等相关课程的教学参考书,旨在培养和提高学生参加ACM国际大学生程序设计竞赛的兴趣。

本书获得浙江省高等教育课堂教学改革(kg2013524,kg20160558)、浙江工业大学精品课程(2015年)、浙江工业大学首届SPOC课程建设项目(2016年)和绍兴市精品课程建设项目(2015年)的大力支持,并得到清华大学出版社编辑张玥、常建丽的热情帮助,在此表示感谢。

由于作者水平所限,书中难免有不足之处,恳请广大读者批评指正。

作者

2019年4月于杭州

①吴文虎，孙贺.程序设计中的组合数学［M］.北京: 清华大学出版社，2005.