信息技术培训基础知识 | FFY's Blog

一、高精度计算

（至少掌握加减乘（高精对高精），正数高精度（简化模板）加减乘除（高精度与低精度）

二、排序算法

基本算法（选择排序、插入排序、冒泡排序、快排、堆排、归并排序、计数排序、基数排序。另外练习字符串排序、多关健字排序、排序二叉树）
典型应用
逆序对、第K小数

三、查找算法

数组映射、顺序查找、二分查找（一般静态）、hash查找（可动态也可静态、编码）

四、递归、回溯、深搜

从相关题目加深理解
最大公约数（减法和求余）、排列数的输出、组合数的输出、表达式计算、逆波兰式、连续最大和（递归）、上台阶问题、跳马问题、填数问题、老鼠走迷宫、因式分解、素数环、皇后问题、机器分工、数的划分、任务安排、四色问题、邮票问题、埃及分数、生日蛋糕、八数码问题、路由选择。（迭代思想、剪枝技巧、IDA*、阶乘编码）

五、广搜

魔板问题、跳棋问题、八数码问题、奇怪的电梯、翻硬币问题。（相关的优化，加快判重、双向搜索、IDA*）

六、二分

二分加速、二分查找、二分枚举

七、数据结构

栈（表达式计算）、队列（广搜中常用、单调队列）、链表、双向链表、堆、竞赛树、排序二叉树、树状数组、hash、并查集、KMP算法、RMQ、LCA、回文串问题、trie。（树的线型化应用、深搜序的应用）

八、图论

图的两种遍历方式、图的连通性判别定（深搜索、并查集）、有向图的强连通分量（两次深搜求交法、tarjan)、拓朴排序、关键路、最短路算法（dijk、floyd、bellman、spfa)、最小生成树（prime、Kruskal）二分匹配（最大独立集、最小支配集、最小路径点覆盖问题）（题库上题目较多）欧拉路和欧拉回路、哈密顿回路、关节点、桥

九、动态规划

（重中之重 练习相关基本模型）

重要思想：

二分、逆向思维