目录
第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.8ZOJ1004Anagrams by Stack
2.9ZOJ1094Matrix Chain Multiplication
2.10ZOJ1011NTA
2.11ZOJ1062Trees Made to Order
2.12ZOJ1097Code the Tree
2.13ZOJ1156Unscrambling Images
2.14ZOJ1167Trees on the Level
2.15ZOJ1016Parencodings
2.16ZOJ1944Tree Recovery
2.17ZOJ2104Let 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.3ZOJ1633Big 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.501背包问题
4.5.1递归关系分析
4.5.2算法实现
4.6最长单调递增子序列
4.7数字三角形问题
4.8ZOJ1027Human Gene Functions
4.9ZOJ1074To the Max
4.10ZOJ1093Monkey and Banana
4.11ZOJ1107FatMouse and Cheese
4.12ZOJ1108FatMouses Speed
4.13ZOJ1147Formatting Text
4.14ZOJ1149Dividing
4.15ZOJ1163The Staircases
4.16ZOJ1183Scheduling Lectures
4.17ZOJ1196Fast Food
4.18ZOJ1206Win the Bonus
4.19ZOJ1227Free Candies
4.20ZOJ1234Chopsticks
上机练习题
第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.9ZOJ1012Mainframe
5.10ZOJ1025Wooden Sticks
5.11ZOJ1029Moving Tables
5.12ZOJ1076Gene Assembly
5.13ZOJ1161Gone Fishing
5.14ZOJ1171Sorting the Photos
5.15ZOJ2109FatMouse Trade
上机练习题
第6章回溯算法
6.1回溯算法的理论基础
6.1.1问题的解空间
6.1.2回溯算法的基本思想
6.1.3子集树与排列树
6.2装载问题
6.301背包问题
6.4图的m着色问题
6.5n皇后问题
6.6旅行商问题
6.7流水作业调度问题
6.8子集和问题
6.9ZOJ1145Dreisam Equations
6.10ZOJ1157A Plug for UNIX
6.11ZOJ1166Anagram Checker
6.12ZOJ1213Lumber Cutting
上机练习题
第7章分支限界算法
7.1分支限界算法的基本理论
7.1.1分支限界算法策略
7.1.2分支结点的选择
7.1.3提高分支限界算法的效率
7.1.4限界函数
7.2单源最短路径问题
7.3装载问题
7.401背包问题
7.5旅行商问题
7.6ZOJ1136Multiple
7.7回溯算法与分支限界算法的比较
上机练习题
第8章图的搜索算法
8.1图的深度优先搜索遍历
8.2ZOJ1002Fire Net
8.3ZOJ1008Gnome Tetravex
8.4ZOJ1047Image Perimeters
8.5ZOJ1084Channel Allocation
8.6ZOJ1142Maze
8.7ZOJ1190Optimal Programs
8.8ZOJ1191The Die Is Cast
8.9ZOJ1204Additive equations
8.10ZOJ1245Triangles
8.11ZOJ2100Seeding
8.12图的广度优先搜索遍历
8.13ZOJ1079Robotic Jigsaw
8.14ZOJ1085Alien Security
8.15ZOJ1103Hike on a Graph
8.16ZOJ1148The Game
8.17ZOJ1217Eight
8.18ZOJ1091Knight Moves
上机练习题
第9章图论
9.1网络流问题
9.1.1流和割的概念
9.1.2剩余网络和增广路径
9.1.3FordFulkerson算法
9.1.4EdmondsKarp算法
9.1.5ZOJ1734Power Network——EdmondsKarp算法
9.1.6ISAP算法
9.1.7ZOJ1734Power Network——ISAP算法
9.1.8Dinic算法
9.1.9ZOJ1734Power Network——Dinic算法
9.1.10最小费用流——SPFA算法
9.1.11ZOJ2404Going Home——SPFA算法
9.2二分图匹配问题
9.2.1匹配问题
9.2.2二分图最大匹配——匈牙利算法
9.2.3ZOJ1137Girls and Boys
9.2.4ZOJ1140Courses——匈牙利算法
9.2.5PJU1247The Perfect Stall——匈牙利算法
9.2.6HopcroftKarp算法
9.2.7ZOJ1140Courses——HopcroftKarp算法
9.2.8PJU1274The Perfect Stall——HopcroftKarp算法
9.2.9二分图最佳匹配——Kuhn Munkres算法
9.2.10ZOJ2404Going Home——Kuhn Munkres算法
上机练习题
第10章数论
10.1扩展欧几里得算法
10.2PJU2115C Looooops
10.3欧拉函数
10.4ZOJ1906Relatives
10.5PJU2480Longges problem
10.6PJU3696The Luckiest number
10.7中国剩余定理
10.8ZOJ1160Biorhythms
10.9一元线性同余方程组
10.10PJU2891Strange Way to Express Integers
10.11HDU1573X问题
上机练习题
第11章组合数学
11.1母函数
11.1.1普通型母函数
11.1.2指数型母函数
11.1.3Stirling数
11.1.4Catalan数
11.2HDU2082找单词
11.3HDU1521排列组合
11.4HDU2065“红色病毒”问题
11.5HDU3625Examining the Rooms
11.6POJ2084Game of Connection
11.7容斥原理与鸽巢原理
11.7.1容斥原理
11.7.2错排问题
11.7.3鸽巢原理
11.8HDU2048“恭喜你,中奖了!”
11.9POJ2356Find a multiple
11.10ZOJ2836Number Puzzle
上机练习题
参考文献