省选复习第一弹——知识点总结

2016.02.20 08:54 Sat | 167次阅读 | 旧日oi | 固定链接 | 源码

进度:整理基本完成,每种分类基本按难度从小到大排列?带*号的为没写过的

写在前面……

虽然说是知识点,然而NOIP以上不是没有范围了嘛(雾
想一想还挺难写全的,先把自己做过的题都看一遍,然后再脑补一下没写过的……
一个漫长的计划,希望一个上午能解决?(3.12upd:都快过了1个月了还没弄完……)
不知不觉也变成了BZOJ800+选手了呢。
BZOJ的第一条交题记录


到现在已经过去了将近1年半的时间了,这期间(截止至2016/2/20/9:16),共有510890个交题记录
而我的824道题也占了其中的0.16%呢,虽然是水题set,但想想还是挺有成就感的~果然坚持做一件事就会有收获

这也是我最后一次省选了,为了不给自己留下遗憾,加油吧!

算法

数论

快速幂
exgcd
质因数分解
卢卡斯定理
中国剩余定理
费马小定理
线性筛
组合数取模
组合计数(catalan,stirling,bell……)
快速阶乘
原根
指标
bsgs
exbsgs
概率与期望
莫比乌斯反演 
Rabin-Miller算法
Pollard-Rho  
真欧几里得算法
扩展中国剩余定理(HDU1573)
泰勒/麦克劳林展开
生成函数
指数级生成函数
整数划分
k次方和公式(杜教ppt)
狄利克雷卷积
(n^{2/3}筛法
*拉格朗日乘数法

多项式

FFT/NTT
FWT(and or xor)
分治FFT   
拉格朗日插值
牛顿插值
多项式求逆
多项式求exp
多项式求ln
多项式开根
多项式除法
多点求值

线性变换

矩阵乘法(求前缀和)
高斯消元(+bitset)
倍增floyd
拟阵
线性基
矩阵树定理(有向/无向)
线性规划单纯形
矩阵求逆

字符串

hash
KMP(广义)
KMP树
manacher
最小表示法
后缀数组

图论

邻接表
bfs/dfs
二分图染色
拓扑排序
dij/spfa/floyd
johnson
prim
kruskal
欧拉回路(有向/无向)
二进制枚举+spfa    
spfa负环
floyd最小环+方案(POJ 1734)
差分约束    
次小生成树
二分图最大匹配
二分图最大独立点集
二分图最大团
拓扑图最大独立点集  
强连通分量
点/边双联通分量
稳定婚姻问题
2-SAT
倍增floyd
bitset传递闭包
带花树
二分图最大权匹配
*带权带花树
分块优化dij
线段树优化加边
平面图转对偶图   
矩阵树定理(有向/无向)
曼哈顿距离最小生成树
k短路(A*,可并堆)
斯坦纳树
朱刘算法
k小割
dominator tree
仙人掌相关

dfs序
树的直径
倍增lca
树分块
树链剖分
dfs序换根
树链求交    
prufer编码
树的点分治/动态点分治
lca单调性
虚树
树上莫队

网络流

最大流
最小割
最小费用最大流
最大权闭合图
最大密度子图
竞赛图
最小割树
上下界网络流
最小割唯一性
混合图欧拉回路

计算几何

点积/叉积
线段/直线求交
向量旋转
凸包
半平面交
圆求交
爬山
模拟退火
旋转卡壳
splay维护凸包
平面图转对偶图
扫描线(+线段树)
随机增量法
simpson积分
*圆的反演
*平面图点定位

动态规划及优化

背包
区间dp
树形dp
状压dp
拓扑图dp
单调队列
斜率优化
决策单调性
四边形不等式
凸壳
矩乘
误差dp
概率DP
插头dp
数位dp
未卜先知dp
fft优化dp

博弈、游戏

见dzn ppt……

构造

前缀和思想(CF618F)
拆点思想(BZOJ3724)
黑白染色思想

其它

打表
分治,贪心
排序(快排,归并,冒泡……)
离散化
判断区间联通性
区间加,区间求和(多维)
二分,二分答案,三分
bfs+hash,A*,IDA*,迭代加深
最大子矩阵
随机化算法
随机增量法
置换(乘方,开方)
置换群(Burnside,Polya)
切比雪夫->曼哈顿距离
2-SAT(暴力,tarjan)
分块
莫队
弦图
cdq分治
整体二分
哈夫曼树
01分数规划(二分法,迭代法)
平面最近点对  
动态二分图
动态联通块问题
动态最小生成树

数据结构

数组
队列
栈
链表
ST表
并查集 
带权并查集    
dacing links
优先队列
树状数组
线段树(lazy标记)
zkw线段树
划分树
treap
splay
树套树
可并堆
启发式合并
线段树合并
LCT
KD-TREE

STL

set
map
list
queue
deque
stack
bitset
vector
pbds堆

可持久化

Trie树
线段树
左偏树
并查集
平衡树

字符串

Trie树
ac自动机  
回文自动机 
后缀自动机
广义后缀自动机

一些结论或有趣的方法

BZOJ1875
BZOJ4401
BZOJ1495
BZOJ2048
BZOJ2119
BZOJ2802
BZOJ3000
BZOJ1138
BZOJ1907
BZOJ1074
BZOJ3763
BZOJ1488
BZOJ3563
物理题BZOJ3695