NOIP 算法总结
先贴一张图
(来自 啊哈磊的专栏)
图论
最短路
(1)Floyd
for(int k = 1; k <= N; k++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
A[i][j] = A[i][k] + A[k][j];
- 1
- 2
- 3
- 4
(2)堆优化 Dijkstra
用 priority_queue 做堆,对于每次弹出的点
标记访问
对于所有能访问到的点
松弛
若未访问,压入堆中
- 1
- 2
- 3
- 4
- 5
(3)Spfa
用 queue 做队列,对于每次弹出的点
消除标记
对于所有能访问的点
松弛
若未标记,则标记,进入队列
- 1
- 2
- 3
- 4
- 5
最小生成树
(1)Kruskal
并查集初始化
边权排序
如果边上两点不在同一集合内
合并两点
将边加入最小生成树
- 1
- 2
- 3
- 4
- 5
(2)Prim
//定义集合 A B
任选 A 中一个节点,并加入 B
删除该节点
选一个在所有连接 A 和 B 权值最小的边
将两个节点连接
边数++
将 A 中节点删除并加入到 B 中.
若边数为n-1
完成最小生成树
否则
继续选择
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
强连通分量
Tarjan
对于 Dfs 每次到的节点
初始化 dfn[x] = low[x] = ++dfs_clock
把节点压入栈中
对于所有能访问到的节点
如果 dfn 为 0(未Dfs到)
Dfs 该节点
更新 low[x] = min(low[x], low[该节点])
若不为 0 且 不在栈中
low[x] = min(low[x], dfn[该节点])
如果 low[x] == dfn[x]
弹出栈中元素,直到弹出的元素等于x
则弹出的元素属于一个强连通分量
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
排序
一言不合就 sort
数论&数学
【本人很懒】
搜索
深搜
void Dfs(/*当前状态*/){
if(/*满足结束条件*/){
/*记录最优解*/
return;
}
for(int i = a; i <= b; i++){
/*由i生成新的当前状态*/
/*标记新状态*/
if(/*新状态满足约束条件*/ && /*新状态可能成为答案*/){
dfs(/*新状态*/);
}
/*恢复当前状态*/
}
return ;
}//by ZRT
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
优化:
最优化剪枝
可行性剪枝
记忆化搜索
改变搜索顺序
优化搜索策略
广搜
void Bfs(){
while(!q.empty()){
X = q.front();
for(int i = a; i <= b; i++){
/*由i生成新状态Y*/
if(/*Y合法,并且第一次访问到*/){
q.push(Y);
}
}
q.pop();
}
return ;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
优化:
判重:hash、二叉搜索树
双向广搜
启发式搜索
二分
改写成A*
动态规划
倒推
F[n] = 初值
for(k = n+1; k >= 1; k--)//阶段
for(i; ; )//状态
for(j; ; )//决策
F[k] = opt{F[k+1]+A[k, x]}
print F[1]
- 1
- 2
- 3
- 4
- 5
- 6
顺推
F[1] = 初值
for(k = 2; k <= n; k++)//阶段
for(i; ; )//状态
for(j; ; )//决策
F[k] = opt{F[k-1]+A[k-1, x-1]}
print F[n]
- 1
- 2
- 3
- 4
- 5
- 6
博弈论
分治
二分法
回溯
高级数据结构
二叉树 & 二叉搜索树
并查集
线段树 & 树状数组
字符串
KMP
Manacher
最小表示法
.
.
.
概率与期望
其它
并不全是NOIP考点
1、网络流
2、计算几何
3、FFT
4、LCA
5、2-SAT
6、单纯形法
7、AC自动机
.
.
.
未完待续