NOIP提高组(CSP-S)复赛知识点汇总

基础算法

贪心

枚举

分治

二分答案

倍增

*构造

高精

模拟

*分数规划

图论

图论入门

最短路算法

单源最短路:从一个点到其他所有点的最短路

算法:Dijkstra、spfa、

多源最短路:从所有点到另外点的最短路

算法:Floyd

差分约束

最小生成树(kruskal、prim)

并查集(扩展域)

拓扑排序

二分图染色

*二分图匹配

tarjan找scc、桥、割点,缩点

LCA

树的直径、树的重心

dfs序

*树链剖分

数论

gcd、lcm

埃氏筛法

exgcd,求解同余方程、逆元

快速幂

*组合数学

矩阵

*高斯消元

数据结构

链表

队列(单调队列)、栈(单调栈)

st表

hash表

线段树、树状数组

字典树

*分块

*平衡树

*主席树

*莫队

动态规划

背包DP

树形DP

记忆化搜索

递推

区间DP

序列DP

*概率DP

*DP优化(不涉及斜率优化、四边形不等式等等)

搜索

暴搜(dfs、bfs)

搜索的剪枝

启发式搜索(A∗)

迭代加深搜索、*IDA∗

*随机化搜索

其他算法

STL的基本使用方法

脑洞的正确使用方法

*KMP

*状态压缩

*AC自动机

发表评论

电子邮件地址不会被公开。 必填项已用*标注