目录
计算几何
图论
动态规划
字符串
数论
计数
多项式
数据结构
模板复习
计算几何
（1）计算几何基础
极角排序,atan2与叉积均可，叉积要注意象限
两直线交点：画图，利用面积比算长度比
node dot(line x,line y) {return y.p+(crs(x.v,x.p-y.p)/crs(x.v,y.v))*y.v;}（1）凸包，闵可夫斯基和
选出最左下的点，极角排序后单调栈维护。
凸包与凸包的闵可夫斯基和仍是凸包
边仍是原来两个凸包的边，据此直接极角排序后合并。
（1）半平面交
朱泽园排序增量法
类似凸包那样极角排序，用个双端队列维护，如果队末的两个半平面交点在当前半平面之外就把队末弹掉
队头也要一样处理，最后要把伸出去的部分弹掉。
https://blog.csdn.net/hzj1054689699/article/details/88929383
（1）KD树、平面最近点对
KD树理解起来很简单，实现也不算难
平面最近点对直接暴力在KD树上找，如果到当前矩形的最短距离都大于当前答案就退出。
（1）旋转卡壳、平面最远点对
逆时针枚举每个点，其最远点显然是单调且单峰的，直接用个指针扫过去即可。
（1）辛普森积分
用一个二次函数去拟合，用来搞什么圆的面积并或者面积交之类的非常好用。
公式：S(l,r)=(r-l)/6*(F(l)+4F((l+r)/2)+F(r))
递归计算，当更深一层算出的值与当前层差距很小则退出。
（1）线性规划（单纯形）
实在不知道怎么写。。
老实背板吧
https://blog.csdn.net/hzj1054689699/article/details/88260176
图论
（1）支配树
有一定理解难度，代码比较简洁。
https://blog.csdn.net/hzj1054689699/article/details/93531732
（）网络流相关（二元关系，最大权闭合子图、最长反链，上下界网络流）
套路：什么依赖、必须选、捆绑，不能同时选之类的东西可以用INF的边来搞
考虑最小割的意义
带负环的费用流：强制满流（加个下界），连一条它的反边即可
最长反链的最小链覆盖
网格图上可以考虑黑白染色
（1）差分约束系统
直接最短路...
（1）欧拉回路
路径条件：连通，无向图：至多两个奇点 有向图：两个点一个出度和入度不等且差1
回路条件：连通，无向图：全为偶点 有向图：入度等于出度
逐步插入回路法：DFS，回溯时将当前点压入栈，最后倒序输出。注意跑的时候要删边
（1）2-SAT
拆点表示TRUE和FALSE
连边x,y代表选了x必须选y
对应点在一个强联通分量则无解
找可行解：
tarjan缩点，按照原本的边反向走，拓扑逆序来做，选了一个点以后，对应点所在强联通分量和指向的点全不能选。
https://blog.csdn.net/hzj1054689699/article/details/78904639
（1）点双连通分量，圆方树
与边双不同的是在枚举出边的时候弹栈，除了当前点全部弹掉，当前点也要算进去
（）二分图匹配、带权匹配KM
KM可以用费用流替代，暂且不管
（1）一般图匹配——带花树
背板，没什么好说的。
https://blog.csdn.net/hzj1054689699/article/details/88667614
动态规划
（）树形依赖DP，数位DP、斜率优化DP，决策单调性，凸优化
（）动态DP
（）各种各样奇怪的DP模型
搜索、博弈
（）SG函数
（）A*,IDA*
（）Nim游戏
（）模拟退火
字符串
（）KMP
（）扩展KMP
（）AC自动机
（）SA
（）SAM
（）manacher
（）回文自动机（回文树）
（）哈希
数论
（）莫比乌斯反演、杜教筛
（）洲阁筛
（）类欧
（）Miller_Rabin、Pollard_Rho
（）中国剩余定理，扩展中国剩余定理
计数
（）概率与期望
（）斯特林容斥，斯特林反演
（）组合数、斯特林数、卡特兰数、容斥
（）图的计数（无向连通图计数）
（）拉格朗日反演
（）拆分数
会根号做法就好了...，显然数最多只有根号种，每次考虑要么新加一个要么之前的全部+1
多项式
（）Berlekamp-Massey
（1）自然数幂和（伯努利数）、生成函数、拉格朗日插值法
自然数幂和斯特林数和差分表都挺好弄
拉格朗日插值法可能要稍微推一下
伯努利数要记
（1）FFT、NTT
（1）多项式求逆，多项式取模，多项式开根，多点求值
多点求值应该不会考吧（狗头）
（1）多项式exp，多项式ln
可以现场推式子
（1）循环卷积
可以现场推式子
数据结构
（）点分治，CDQ分治（整体二分）
（）虚树
（）树链剖分
（）树套树（树状数组套线段树）
（）主席树
（）平衡树（splay）
（）LCT
（）二进制分组
（）平衡树套线段树（bzoj3065）
模板复习
（）exKMP
（）LCT
（）FFT、NTT
（）min_25筛
（）多项式求逆，多项式取模，多项式开根，多点求值，多项式ln，多项式exp
（）Miller_Rabin、Pollard_Rho
（）回文树
（）SA、SAM
（）欧拉回路