Back to Posts

Summary of algorithm syllabus in OI

Posted in  OI

数据结构:

	Splay—>

	线段树—>感觉这是我掌握的不错的一个数据结构了,已经可以当工具来用了
   		
	主席树—>感觉这个东西并不常考
   		
	可并堆—>不会
   		
	树状数组—>好像线段树就OK吧,但树状数组常数小啊
	
	可持久化思想

图论:

	2—SAT
	
	Tarjan
	
	网络流: 最小割,最大流(掌握的不错),二分图之类的东西,费用流
	
	分层图什么的,不会
	
	割点、边,桥啥的,只会打板子,一道题都没做过

DP:

DP类型:

	背包
	
	基本线性DP/区间DP

	计数DP

	数位DP
	
	状压DP
	
	树形DP

	插头DP
	
DP优化:

	斜率优化—>全都是板子

	单调队列优化—>主要是要求被弹掉的决策是不会在成为最优决策的

	四边形不等式优化—>好像没啥用啊

	改变DP顺序优化DP

数学:

	基础:gcd,lcm,费马小定理,逆元,扩欧,欧拉函数

	质数,约数,同余
	
	矩阵乘法(能加速好多东西吧)

	高斯消元与线性空间
	
	组合数
	
	容斥原理

	概率与期望

	博弈论与SG函数
	
	行列式
	
	线性基
	
	FFT等数学典型题型

字符串相关:

	KMP:这是NOIP算法吧
	
	后缀数组:实际上我掌握的差不多了吧
	
	AC自动机:不会
	
	Trie树:就会0/1Trie
	
	Hash:不会

分治:

	CDQ分治

	整体二分

基本算法:

	位运算——这东西应该有好多好多的比较神的用法
	
	倍增
	
	贪心——反正没思路就贪心呗

构造与交互题是smg

转了一个dalao的水题推荐csyzcyj

最喜欢水题了

Read Next

Problem