目录

第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.10ZOJ1097Code the Tree

2.11ZOJ1156Unscrambling Images

2.12ZOJ1167Trees on the Level

2.13ZOJ1016Parencodings

2.14ZOJ1944Tree Recovery

2.15ZOJ2104Let the Balloon Rise

上机练习题

第3章递归与分治策略

3.1递归算法

3.1.1斐波那契数列

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.3ZOJ1633Big String

3.4洛谷P1182 数列分段 Section Ⅱ

3.5洛谷P1824 进击的奶牛

3.6洛谷P1873砍树

3.7洛谷P1908逆序对

上机练习题

第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.10ZOJ1107FatMouse and Cheese

4.11ZOJ1108FatMouses Speed

4.12ZOJ1163The Staircases

4.13ZOJ1196Fast Food

4.14ZOJ1234Chopsticks

4.15ZOJ3211 Dream City

4.16ZOJ3956 Course Selection System

4.17洛谷P2758编辑距离

4.18洛谷P1130红牌

4.19洛谷P1063能量项链

4.20洛谷P2016 战略游戏

4.21洛谷P1352 没有上司的舞会

4.22洛谷P1122 最大子树和

4.23洛谷P2014 选课

4.24洛谷P2015二叉苹果树

上机练习题

第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.8ZOJ1012Mainframe

5.9ZOJ1025Wooden Sticks

5.10ZOJ1076Gene Assembly

5.11ZOJ2109FatMouse Trade

5.12洛谷P1717 钓鱼

5.13洛谷P1230智力大冲浪

5.14洛谷U167571信使

5.15HDU1863 畅通工程

5.16洛谷P2330 繁忙的都市

上机练习题

第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.9ZOJ1457Prime Ring

6.10ZOJ2110Tempter of the Bone

6.11ZOJ2734Exchange Cards

6.12洛谷P1378 油滴扩展

6.13经典题——工作分配问题

6.14洛谷P1692 部落卫队

上机练习题

第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

上机练习题

第8章图的搜索算法

8.1图的深度优先搜索遍历

8.2ZOJ1002Fire Net

8.3ZOJ1047Image Perimeters

8.4ZOJ1191The Die Is Cast

8.5ZOJ1204Additive equations

8.6ZOJ2100Seeding

8.7洛谷P1162填涂颜色

8.8洛谷P1363幻象迷宫

8.9洛谷P1605 迷宫

8.10洛谷P2895 Meteor Shower S

8.11POJ1164 The Castle

8.12图的广度优先搜索遍历

8.13ZOJ1148The Game

8.14ZOJ1091Knight Moves

8.15经典算法题——迷宫的最短路径

8.16洛谷P1983 车站分级

8.17洛谷P2802 回家

8.18洛谷P4554小明的游戏

8.19ZJU1649 Rescue

上机练习题

第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

上机练习题

参考文献