清华科技大讲堂 算法竞赛入门到进阶 作者:罗勇军 出版时间:2019年版丛编项: 清华科技大讲堂内容简介 本书是算法竞赛的入门和进阶教材,包括算法思路、模板代码、知识体系、赛事相关等内容。本书把竞赛常用的知识点和竞赛题结合起来,讲解清晰、透彻,帮助初学者建立自信心,快速从实际问题入手,模仿经典代码解决问题,进入中级学习阶段。 全书分为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.1vector 3.1.2栈和stack3.1.3队列和queue3.1.4优先队列和priority_queue3.1.5链表和list3.1.6set3.1.7map3.2sort()3.3next_permutation()第4章搜索技术4.1递归和排列 4.2子集生成和组合问题4.3BFS4.3.1BFS和队列 4.3.2八数码问题和状态图搜索4.3.3BFS与A*算法 4.3.4双向广搜4.4DFS4.4.1DFS和递归4.4.2回溯与剪枝4.4.3迭代加深搜索4.4.4IDA*4.5小结第5章高级数据结构5.1并查集 5.2二叉树5.2.1二叉树的存储5.2.2二叉树的遍历 5.2.3二叉搜索树5.2.4Treap树 5.2.5Splay树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.3Huffman编码 6.1.4模拟退火6.1.5习题6.2分治法6.2.1归并排序6.2.2快速排序 6.3减治法6.4小结第7章动态规划7.1基础DP7.1.1硬币问题7.1.20/1背包 7.1.3最长公共子序列7.1.4最长递增子序列7.1.5基础DP习题7.2递推与记忆化搜索 7.3区间DP7.4树形DP7.5数位DP7.6状态压缩DP 7.7小结第8章数学8.1高精度计算 8.2数论8.2.1模运算8.2.2快速幂8.2.3GCD、LCM8.2.4扩展欧几里得算法与二元一次方程的整数解8.2.5同余与逆元8.2.6素数8.3组合数学8.3.1鸽巢原理8.3.2杨辉三角和二项式系数8.3.3容斥原理8.3.4Fibonacci数列8.3.5母函数 8.3.6特殊计数8.4概率和数学期望8.5公平组合游戏 8.5.1巴什游戏与Pposition、Nposition8.5.2尼姆游戏8.5.3图游戏与SpragueGrundy函数8.5.4威佐夫游戏8.6小结第9章字符串9.1字符串的基本操作9.2字符串哈希 9.3字典树9.4KMP 9.5AC自动机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.1Kosaraju算法 10.7.2Tarjan算法10.82SAT问题 10.9最短路10.9.1FloydWarshall10.9.2BellmanFord 10.9.3SPFA10.9.4Dijkstra10.10最小生成树10.10.1prim算法10.10.2kruskal算法10.11最大流10.11.1FordFulkerson方法 10.11.2EdmondsKarp算法10.11.3Dinic算法和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.1ICPC亚洲区域赛(中国大陆)情况12.2ICPC区域赛题目解析 12.2.1F题Friendship of Frog(hdu 5578)12.2.2K题Kingdom of Black and White(hdu 5583)12.2.3L题LCM Walk(hdu 5584)12.2.4A题An Easy Physics Problem(hdu 5572)12.2.5B题Binary Tree(hdu 5573)12.2.6D题Discover Water Tank(hdu 5575)12.2.7E题Expection of String(hdu 5576)12.2.8G题Game of Arrays(hdu 5579)12.2.9I题Infinity Point Sets(hdu 5581)参考文献 上一篇: 程序员进阶心法:快速突破成长瓶颈 胡峰 2019年版 下一篇: 谁说菜鸟不会数据分析 Python篇 方小敏 2019年版