蓝桥杯算法考点

Question

如题所述

Answer 1

蓝桥杯算法考点：

基础算法。一星：打表，枚举，倍增，离散化，差分。二星：分治法，贪心（Huffman编码）， 尺取法， 二分法，三分法，整体二分，ST算法。

搜索。一星：基本DFS，基本BFS。二星：DFS记忆化搜索，IDA* BFS扩展（双向广搜，优先队列，双端队列），剪枝，爬山算法，随机增量法，模拟退火。三星：A*。

高级数据结构。一星：并查集（带权），分块。二星：莫队算法（树上莫队） 树状数组，线段树 可持久化线段树，二叉搜索树，treap树，替罪羊树，块状链表。三星：splay树，LCT，树套树，猫树，CDQ分治，舞蹈链，左偏树，后缀平衡树，KDtree。

动态规划：DP问题的性质（重叠子问题，最优子结构，无后效性），编码方法（记忆化递归，递推），滚动数组，常见线性DP（0/1问题，分组背包，多重背包，最长公共子序列（LCS），最长递增子序列（LIS），编辑距离，最小化分，行走问题，矩阵最长递增路径，子集和问题，矩阵链乘法，布尔括号问题）。

区间DP，状态压缩DP，树形DP，数位DP，计数类DP，概率DP。插头DP，基环树DP，DP优化（数据结构优化，单调队列优化，斜率优化，分治优化，四边形不等式优化）。