算法设计与分析：以ACM大学生程序设计竞赛在线题库为例（微课版）

　　本书内容包括经典的算法设计技术，主要介绍数据结构和标准模板库、递归与分治策略、动态规划、贪心算法、回溯算法、分支限界算法、图的搜索算法、图论、数论和组合数学问题。本书包括大量的问题实例，并在北京大学、浙江大学和杭州电子科技大学在线题库中精选原题，详细地分析解题的方法，深入浅出地讲解用到的算法，章后的上机练习题也选自在线题库中的典型题目，供读者练习，以巩固所学算法。本书内容基本上涵盖了目前大学生程序设计竞赛所要掌握的算法。 本书结构清晰、内容丰富，适合作为计算机科学与技术、软件工程以及相关学科算法课程的教材或参考书，特别适合有志于参加信息学竞赛和ACM大学生程序设计竞赛的读者学习和训练。

　　赵端阳，教授，1987年中国矿业大学硕士研究生毕业，留校工作两年，1989-1999，杭州市杭州船舶工业学校任教，1999年并入浙江工业大学。从1987年起，一直从事计算机专业课程的教学。2002.9～2003.7，到英国Plymouth大学网络研究组，作为高级访问学者从事网络安全的研究。作者在工作期间一直从事算法设计与分析的研究，从2005年起就一直指导学生参加大学生程序设计竞赛，并每年都获得浙江省大学生程序设计竞赛的银牌和铜牌，2017年度，获得ACM大学生程序设计竞赛青岛和南宁赛区的铜牌，和东亚赛区的铜牌。编写《算法分析与设计—以大学生程序设计竞赛为例》教程，清华大学出版社，2012年3月出版，2015年改版；编写《ACM大学生程序设计竞赛题解（1）》和《ACM大学生程序设计竞赛题解（2）》，电子工业出版社，2010年7月出版。从2007年起承担本科《算法分析与设计》课程的教学，本课程2013年评为浙江工业大学精品课程，2013年，获得浙江省课堂教学改革SPOC立项。2015年版《算法设计与分析—以ACM大学生程序设计竞赛在线题库为例》获得浙江省“十二五优秀教材”，浙江省“十三五”新形态教材立项。

第1章算法概述
1．1引言
1．1．1算法的描述
1．1．2算法的设计
1．2算法的复杂度
1．2．1时间复杂度
1．2．2空间复杂度
1．3大学生程序设计竞赛概述
1．4程序设计在线测试题库
第2章数据结构和标准模板库
2．1栈
2．2向量
2．3映射
2．4列表
2．5集合
2．6队列
2．7优先队列
2．8ZOJ1004Anagrams by Stack
2．9ZOJ1094Matrix Chain Multiplication
2．10ZOJ1011NTA
2．11ZOJ1062Trees Made to Order
2．12ZOJ1097Code the Tree
2．13ZOJ1156Unscrambling Images
2．14ZOJ1167Trees on the Level
2．15ZOJ1016Parencodings
2．16ZOJ1944Tree Recovery
2．17ZOJ2104Let the Balloon Rise
上机练习题
第3章递归与分治策略
3．1递归算法
3．1．1Fibonacci数列
3．1．2集合的全排列问题
3．1．3整数划分问题
3．2分治策略
3．2．1分治策略的基本步骤
3．2．2分治策略的适用条件
3．2．3二分搜索算法
3．2．4循环赛日程表
3．2．5棋盘覆盖问题
3．2．6选择问题
3．2．7输油管道问题
3．2．8半数集问题
3．2．9整数因子分解
3．2．10取余运算
3．3ZOJ1633Big String
上机练习题
 
 
第4章动态规划
4．1矩阵连乘积问题
4．1．1分析解的结构
4．1．2建立递归关系
4．1．3计算值
4．1．4构造解
4．2动态规划算法的基本要素
4．2．1子结构
4．2．2重叠子问题
4．2．3备忘录方法
4．3长公共子序列
4．3．1长公共子序列的结构
4．3．2子问题的递归结构
4．3．3计算值
4．3．4构造长公共子序列
4．4子段和
4．501背包问题
4．5．1递归关系分析
4．5．2算法实现
4．6长单调递增子序列
4．7数字三角形问题
4．8ZOJ1027Human Gene Functions
4．9ZOJ1074To the Max
4．10ZOJ1093Monkey and Banana
4．11ZOJ1107FatMouse and Cheese
4．12ZOJ1108FatMouses Speed
4．13ZOJ1147Formatting Text
4．14ZOJ1149Dividing
4．15ZOJ1163The Staircases
4．16ZOJ1183Scheduling Lectures
4．17ZOJ1196Fast Food
4．18ZOJ1206Win the Bonus
4．19ZOJ1227Free Candies
4．20ZOJ1234Chopsticks
上机练习题
第5章贪心算法
5．1活动安排问题
5．2贪心算法的理论基础
5．2．1贪心选择性质
5．2．2子结构性质
5．2．3贪心算法的求解过程
5．3背包问题
5．4装载问题
5．5单源短路径
5．6小生成树
5．6．1小生成树的性质
5．6．2Prim算法
5．6．3Kruskal算法
5．7删数问题
5．7．1问题的贪心选择性质
5．7．2问题的子结构性质
5．8多处服务次序问题
5．8．1问题的贪心选择性质
5．8．2问题的子结构性质
5．9ZOJ1012Mainframe
5．10ZOJ1025Wooden Sticks
5．11ZOJ1029Moving Tables
5．12ZOJ1076Gene Assembly
5．13ZOJ1161Gone Fishing
5．14ZOJ1171Sorting the Photos
5．15ZOJ2109FatMouse Trade
上机练习题
第6章回溯算法
6．1回溯算法的理论基础
6．1．1问题的解空间
6．1．2回溯算法的基本思想
6．1．3子集树与排列树
6．2装载问题
6．301背包问题
6．4图的m着色问题
6．5n皇后问题
6．6旅行商问题
6．7流水作业调度问题
6．8子集和问题
6．9ZOJ1145Dreisam Equations
6．10ZOJ1157A Plug for UNIX
6．11ZOJ1166Anagram Checker
6．12ZOJ1213Lumber Cutting
上机练习题
第7章分支限界算法
7．1分支限界算法的基本理论
7．1．1分支限界算法策略
7．1．2分支结点的选择
7．1．3提高分支限界算法的效率
7．1．4限界函数
7．2单源短路径问题
7．3装载问题
7．401背包问题
7．5旅行商问题
7．6ZOJ1136Multiple
7．7回溯算法与分支限界算法的比较
上机练习题
第8章图的搜索算法
8．1图的深度优先搜索遍历
8．2ZOJ1002Fire Net
8．3ZOJ1008Gnome Tetravex
8．4ZOJ1047Image Perimeters
8．5ZOJ1084Channel Allocation
8．6ZOJ1142Maze
8．7ZOJ1190Optimal Programs
8．8ZOJ1191The Die Is Cast
8．9ZOJ1204Additive equations
8．10ZOJ1245Triangles
8．11ZOJ2100Seeding
8．12图的广度优先搜索遍历
8．13ZOJ1079Robotic Jigsaw
8．14ZOJ1085Alien Security
8．15ZOJ1103Hike on a Graph
8．16ZOJ1148The Game
8．17ZOJ1217Eight
8．18ZOJ1091Knight Moves
上机练习题
第9章图论
9．1网络流问题
9．1．1流和割的概念
9．1．2剩余网络和增广路径
9．1．3FordFulkerson算法
9．1．4EdmondsKarp算法
9．1．5ZOJ1734Power Network——EdmondsKarp算法
9．1．6ISAP算法
9．1．7ZOJ1734Power Network——ISAP算法
9．1．8Dinic算法
9．1．9ZOJ1734Power Network——Dinic算法
9．1．10小费用流——SPFA算法
9．1．11ZOJ2404Going Home——SPFA算法
9．2二分图匹配问题
9．2．1匹配问题
9．2．2二分图匹配——匈牙利算法
9．2．3ZOJ1137Girls and Boys
9．2．4ZOJ1140Courses——匈牙利算法
9．2．5PJU1247The Perfect Stall——匈牙利算法
9．2．6HopcroftKarp算法
9．2．7ZOJ1140Courses——HopcroftKarp算法
9．2．8PJU1274The Perfect Stall——HopcroftKarp算法
9．2．9二分图匹配——Kuhn Munkres算法
9．2．10ZOJ2404Going Home——Kuhn Munkres算法
上机练习题
第10章数论
10．1扩展欧几里得算法
10．2PJU2115C Looooops
10．3欧拉函数
10．4ZOJ1906Relatives
10．5PJU2480Longges problem
10．6PJU3696The Luckiest number
10．7中国剩余定理
10．8ZOJ1160Biorhythms
10．9一元线性同余方程组
10．10PJU2891Strange Way to Express Integers
10．11HDU1573X问题
上机练习题
第11章组合数学
11．1母函数
11．1．1普通型母函数
11．1．2指数型母函数
11．1．3Stirling数
11．1．4Catalan数
11．2HDU2082找单词
11．3HDU1521排列组合
11．4HDU2065“红色病毒”问题
11．5HDU3625Examining the Rooms
11．6POJ2084Game of Connection
11．7容斥原理与鸽巢原理
11．7．1容斥原理
11．7．2错排问题
11．7．3鸽巢原理
11．8HDU2048“恭喜你，中奖了！”
11．9POJ2356Find a multiple
11．10ZOJ2836Number Puzzle
上机练习题
参考文献