算法设计与分析：以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
上机练习题
参考文献