《算法竞赛入门到进阶》简介:

本书是算法竞赛的入门和进阶教材,包括算法思路、模板代码、知识体系、赛事相关等内容。本书把竞赛常用的知识点和竞赛题结合起来,讲解清晰、透彻,帮助初学者建立自信心,快速从实际问题入手,模仿经典代码解决问题,进入中级学习阶段。

全书分为12章,覆盖了目前算法竞赛中的主要内容,包括算法竞赛概述、算法复杂度、STL和基本数据结构、搜索技术、高级数据结构、基础算法思想、动态规划、数学、字符串、图论、计算几何。

本书适合用于高等院校开展的ICPC、CCPC等算法竞赛培训,中学NOI信息学竞赛培训,以及需要学习算法、提高计算思维的计算机工作者。

《算法竞赛入门到进阶》目录:

目录
第1章 算法竞赛概述
1.1 培养杰出程序员的捷径
1.1.1 编写大量代码
1.1.2 丰富的算法知识
1.1.3 计算思维和逻辑思维
1.1.4 团队合作精神
1.2 算法竞赛与创新能力的培养
1.3 算法竞赛入门
1.3.1 竞赛语言和训练平台
1.3.2 判题和基本的输入与输出
1.3.3 测试
1.3.4 编码速度
1.3.5 模板
1.3.6 题目分类
1.3.7 代码规范
1.4 天赋与勤奋
1.5 学习建议
1.6 本书的特点
第2章 算法复杂度
2.1 计算的资源
2.2 算法的定义
2.3 算法的评估
第3章 STL和基本数据结构
3.1 容器
3.1.1 vector
3.1.2 栈和stack
3.1.3 队列和queue
3.1.4 优先队列和priority_queue
3.1.5 链表和list
3.1.6 set
3.1.7 map
3.2 sort()
3.3 next_permutation()
第4章 搜索技术
4.1 递归和排列
4.2 子集生成和组合问题
4.3 BFS
4.3.1 BFS和队列
4.3.2 八数码问题和状态图搜索
4.3.3 BFS与A*算法
4.3.4 双向广搜
4.4 DFS
4.4.1 DFS和递归
4.4.2 回溯与剪枝
4.4.3 迭代加深搜索
4.4.4 IDA*
4.5 小结
第5章 高级数据结构
5.1 并查集
5.2 二叉树
5.2.1 二叉树的存储
5.2.2 二叉树的遍历
5.2.3 二叉搜索树
5.2.4 Treap树
5.2.5 Splay树
5.3 线段树
5.3.1 线段树的概念
5.3.2 点修改
5.3.3 离散化
5.3.4 区间修改
5.3.5 线段树习题
5.4 树状数组
5.5 小结
第6章 基础算法思想
6.1 贪心法
6.1.1 基本概念
6.1.2 常见问题
6.1.3 Huffman编码
6.1.4 模拟退火
6.1.5 习题
6.2 分治法
6.2.1 归并排序
6.2.2 快速排序
6.3 减治法
6.4 小结
第7章 动态规划
7.1 基础DP
7.1.1 硬币问题
7.1.20 /1背包
7.1.3 最长公共子序列
7.1.4 最长递增子序列
7.1.5 基础DP习题
7.2 递推与记忆化搜索
7.3 区间DP
7.4 树形DP
7.5 数位DP
7.6 状态压缩DP
7.7 小结
第8章 数学
8.1 高精度计算
8.2 数论
8.2.1 模运算
8.2.2 快速幂
8.2.3 GCD、LCM
8.2.4 扩展欧几里得算法与二元一次方程的整数解
8.2.5 同余与逆元
8.2.6 素数
8.3 组合数学
8.3.1 鸽巢原理
8.3.2 杨辉三角和二项式系数
8.3.3 容斥原理
8.3.4 Fibonacci数列
8.3.5 母函数
8.3.6 特殊计数
8.4 概率和数学期望
8.5 公平组合游戏
8.5.1 巴什游戏与P-position、N-position
8.5.2 尼姆游戏
8.5.3 图游戏与Sprague-Grundy函数
8.5.4 威佐夫游戏
8.6 小结
第9章 字符串
9.1 字符串的基本操作
9.2 字符串哈希
9.3 字典树
9.4 KMP
9.5 AC自动机
9.6 后缀树和后缀数组
9.6.1 概念
9.6.2 用倍增法求后缀数组
9.6.3 用后缀数组解决经典问题
9.7 小结
第10章 图论
10.1 图的基本概念
10.2 图的存储
10.3 图的遍历和连通性
10.4 拓扑排序
10.5 欧拉路
10.6 无向图的连通性
10.6.1 割点和割边
10.6.2 双连通分量
10.7 有向图的连通性
10.7.1 Kosaraju算法
10.7.2 Tarjan算法
10.8 2-SAT问题
10.9 最短路
10.9.1 Floyd-Warshall
10.9.2 Bellman-Ford
10.9.3 SPFA
10.9.4 Dijkstra
10.10 最小生成树
10.1 0.1 prim算法
10.1 0.2 kruskal算法
10.11 最大流
10.1 1.1 Ford-Fulkerson方法
10.1 1.2 Edmonds-Karp算法
10.1 1.3 Dinic算法和ISAP算法
10.12 最小割
10.13 最小费用最大流
10.14 二分图匹配
10.15 小结
第11章 计算几何
11.1 二维几何基础
11.1.1 点和向量
11.1.2 点积和叉积
11.1.3 点和线
11.1.4 多边形
11.1.5 凸包
11.1.6 最近点对
11.1.7 旋转卡壳
11.1.8 半平面交
11.2 圆
11.2.1 基本计算
11.2.2 最小圆覆盖
11.3 三维几何
11.3.1 三维点和向量
11.3.2 三维点积
11.3.3 三维叉积
11.3.4 最小球覆盖
11.3.5 三维凸包
11.4 几何模板
11.5 小结
第12章 ICPC区域赛真题
12.1 ICPC亚洲区域赛 (中国大陆) 情况
12.2 ICPC区域赛题目解析
12.2.1 F题Friendship of Frog (hdu 5578)
12.2.2 K题Kingdom of Black and White (hdu 5583)
12.2.3 L题LCM Walk (hdu 5584)
12.2.4 A题An Easy Physics Problem (hdu 5572)
12.2.5 B题Binary Tree (hdu 5573)
12.2.6 D题Discover Water Tank (hdu 5575)
12.2.7 E题Expection of String (hdu 5576)
12.2.8 G题Game of Arrays (hdu 5579)
12.2.9 I题Infinity Point Sets (hdu 5581)
参考文献
· · · · · ·