此仓库是我的OI代码仓库。

该仓库包括：

• Source/Unclassified：源代码
• Review：复习笔记
• Checker：Windows/Linux本地Judger
• Templates：代码模板

希望有一天学弟们可以看到我给他们留下的东西。

高考加油吧。

Review

博弈论

• [x] nim系列游戏
• [x] sg函数
• [x] 对抗搜索 AlphaBeta
• [x] 威佐夫博弈、斐波那契博弈

网络流

• [x] 二分图
• [x] 最大流
• [x] 费用流
• [x] 带上下界网络流
• [x] 常见网络流/最小割模型
• [x] 最小割性质【AHOI2009】最小割
• [x] 消圈定理

数据结构

• [x] 树状数组
• [x] 线段树
• [x] 划分树
• [x] 平衡树（fhqtreap/splay）
• [x] LCT
• [x] 并查集
• [x] kd-tree
• [x] 可并堆
• [x] 可持久化数据结构

数学

数论

• [x] gcd/exgcd
• [x] 费马（线性推逆元）/（EX）欧拉定理
• [x] Miller Rabin
• [x] Pollard Rho
• [x] RSA
• [x] CRT/exCRT
• [x] 线性筛求积性函数值-因子分解
• [x] 狄利克雷卷积，莫比乌斯反演
• [x] 低于线性复杂度筛法
• [x] BSGS/exBSGS
• [x] 原根 映射技巧

集合论/群论

• [x] 置换 Polya定理
• [x] 容斥

组合数学

• [x] Catalan
• [x] Stirling
• [x] lucas/exLucas

多项式

• [x] FFT
• [x] NTT
• [x] FWT
• [x] 实序列DFT
• [x] MTT
• [x] 牛顿迭代法与多项式求逆/取模/ln/exp/三角函数/组合数取模
• [x] FFT封装

线性代数

• [x] 高斯消元
• [x] LUP分解/矩阵求逆
• [x] 行列式
• [x] 线性基
• [x] 最小二乘逼近

其他

• [x] 泰勒展开
• [x] Simpson积分
• [x] 概率期望
• [x] 生成函数/贝尔数/伯努利数求自然数幂和
• [x] 拉格朗日插值法
• [x] 二项式/斯特林/子集反演
• [x] 常见数学公式
• [x] 线性复杂度插值

动态规划

• [x] 背包
• [x] 数位动规
• [x] 插头dp
• [x] LCIS

dp优化

• [x] 单调队列
• [x] 斜率优化
• [x] 四边形不等式
• [x] 矩阵快速幂

图论

树

• [x] LCA
• [x] 树链剖分（重链剖分/长链剖分）
• [x] 树的直径
• [x] 点分治
• [x] 虚树
• [x] purfer序列
• [x] dsu on tree

最短路

• [x] SPFA
• [x] Dijskra
• [x] Floyd
• [x] 差分约束
• [x] k短路

生成树

• [x] Kruskal/Prim
• [x] Kruskal重构树
• [x] 曼哈顿距离最小生成树
• [x] 生成树性质
• [x] MatrixTree定理、扩展
• [x] 斯坦纳树

其他

• [x] 割点，桥
• [x] 强连通分量
• [x] 双连通分量
• [x] 2-SAT
• [x] 仙人掌与圆方树
• [x] 欧拉回路/哈密尔顿回路
• [x] 竞赛图、最小平均值环、平面图性质

字符串

• [x] Hash
• [x] Trie/AC自动机
• [x] 后缀树
• [x] 后缀数组
• [x] 后缀仙人掌
• [x] 后缀自动机
• [x] PAM
• [x] KMP
• [x] Manacher
• [x] Huffman
• [x] 表达式解析

计算几何

• [x] 基础设施-pick定理-切比雪夫距离
• [x] 凸包（在线凸包 /凸包加法/合并/稀疏包分布P614）
• [x] 旋转卡壳
• [x] HPI（WC2012钟诚讲稿-线性判空集）
• [x] 圆的交并/最小圆覆盖/圆的反演
• [x] 平面最近点对

最优化问题

• [x] 爬山法
• [x] 模拟退火（分块模拟退火）
• [x] 遗传算法
• [x] A*算法
• [x] 梯度下降
• [x] 01分数规划

思想/技巧

• [x] 二分
• [x] 三分
• [x] 补集转化
• [x] 莫队-按照奇偶性排序-树上莫队
• [x] 分块
• [x] MITM
• [x] 倍增
• [x] 随机化
• [x] 按位拆分
• [x] 整体二分
• [x] cdq分治
• [x] 扫描线
• [x] 差分
• [x] 双指针法
• [x] 优先队列维护长序列
• [x] 可删堆
• [x] 二进制分组

卡常

• [x] 取模
• [x] 矩阵乘法
• [x] 基于硬件的优化
• [x] 搜索优化
• [x] 位运算技巧 子集枚举
• [x] 数组的清零（对修改部分清零，时间戳）

理论

• [x] 主定理
• [x] NP完全性
• [x] 数值编码

Advance

• [x] 带花树
• [x] 线段树分治
• [x] HLPP
• [x] min_25筛
• [x] Berlekamp-MasseyBy fjzzq2002
• [x] ISAP
• [x] IDA*
• [x] DLX
• [x] 单纯形算法
• [x] Johnson
• [x] 二次剩余、三次剩余、高次剩余
• [x] 拉格朗日乘数法
• [x] 常系数齐次线性递推
• [x] 拉格朗日反演
• [x] 快速莫比乌斯变换
• [x] zkw线段树
• [x] Segment tree beats
• [x] Lindström–Gessel–Viennot lemma
• [x] 最小割树
• [x] 势能分析线段树
• [x] 弦图、最大势算法
• [x] Hall定理
• [x] Raney引理
• [x] 快速凸包
• [x] 康托展开
• [x] Stoer-Wagner算法
• [x] LCT维护子树信息和边权信息
• [x] 共价大爷游长沙技巧
• [x] FFT字符串通配By yyb
• [x] boruvka算法-CF888G
• [x] 动态DP
• [x] ExKMP(Z Algorithm)
• [x] 二维FFT
• [x] 类欧几里得算法
• [x] 三元环By tan90°
• [x] 启发式分裂By zsy
• [x] minmax容斥
• [x] CZTBy myy 再探快速傅里叶变换
• [x] 优化形式幂级数计算的牛顿法的常数By negiizhao
• [x] 回滚莫队
• [x] 原根对1求离散对数By Dance Of Faith
• [x] 集合选数最值一类问题By tkandi
• [x] 子序列自动机
• [x] Dilworth定理
• [x] 杨氏矩阵
• [x] 一个用SAM维护多个串的根号特技By Mangoyang
• [x] IDDFS SPFA判负环By 姜碧野
• [x] 单位根反演 By czy
• [x] GarsiaWachs算法
• [x] 猫树By immortalCO
• [x] Baillie–PSW素性测试
• [x] pollardrho离散对数
• [x] Pohlig–Hellman algorithm
• [x] 利用powerful number求积性函数前缀和By fjzzq2002
• [ ] 模拟费用流
• [x] 生成函数与背包问题
• [x] 多路增广费用流
• [x] 最小表示法
• [ ] 构造问题总结
• [x] 珂朵莉树详解By yzhang
• [x] DP的各种优化By FlashHu
• [x] 线段树分裂、李超线段树、线段树维护单调栈By FlashHu
• [x] 模拟退火调参By FlashHu
• [ ] 母函数求解、优选法、线性常系数齐次递推关系By FlashHu
• [ ] 线段树维护单调子序列By xyz32768
• [x] 配对堆By WAAutoMaton
• [ ] 图上博弈论By 自为风月马前卒
• [ ] 莫比乌斯反演常见套路By 自为风月马前卒
• [x] 球与盒子的组合计数By 自为风月马前卒
• [ ] KMP算法优化
• [ ] zkw线段树常用模板
• [x] O(1)gcdBy fjzzq2002
• [ ] FFT优化By zjt
• [ ] 常见线性规划标准型
• [x] zkw费用流

标准库使用

• [ ] valarray:std::valarrayby SarvaTathagata
• [ ] functional:std::plus/minus等Function Object
• [ ] algorithm:std::partial_sum/std::adjacent_difference
• [ ] bitset:std::bitset
• [ ] cmath:fma,tgamma

Research

• [ ] 有标号的DAG计数By yyb
• [ ] Bron–Kerbosch算法
• [ ] 生成函数与图的计数
• [ ] 最小树型图
• [ ] 平面性算法
• [ ] 点定位
• [ ] 支配树By MoebiusMeow
• [ ] 边分治
• [ ] 欧几里得距离MSTBy zball
• [ ] TS剩余
• [ ] 组合数前缀和By 自为风月马前卒
• [ ] Lyndon WordBy 自为风月马前卒
• [ ] 素数的k次幂前缀和(Meissel-Lehmer) IOI2018 zzt
• [ ] 约数函数前缀和 IOI2018 zzt
• [ ] 轨道-稳定集定理
• [ ] Ukkonen线性构造后缀树By permui
• [ ] Q-learning
• [ ] Karger算法
• [ ] ETT(Euler Tour Tree)By Memphis
• [ ] Top-TreeBy MemphisBy negiizhao
• [ ] fractional cascading
• [ ] 闭包演算法筆記
• [ ] b-Matching演算法筆記
• [ ] Stable Matching演算法筆記
• [ ] Chinese Postman Problem演算法筆記
• [ ] 最小方差生成树
• [ ] 牛顿级数差分
• [ ] 牛顿插值法By 马同学
• [ ] 拟牛顿法BFGS
• [ ] 笛卡尔树 O(n)-O(1) RMQ
• [ ] 三维凸包与Delaunay剖分的关系By 刘汝佳
• [ ] Tutte 矩阵与一般图匹配
• [ ] 特征多项式求法By ftiasch
• [ ] 区间加多项式问题By riteme
• [ ] 近似算法
• [ ] ECC+ECM
• [ ] ID3
• [ ] 卡SPFA
• [ ] 超大斐波那契数取模By ACdreamer
• [ ] 卡Hash By dacin21
• [ ] 卡并查集
• [ ] 最大流算法效率比较
• [ ] 平衡树效率比较
• [ ] NTR算法 By raffica
• [ ] DC3
• [ ] SA-IS算法
• [ ] Chan's algorithm
• [ ] DoubleArrayTrie
• [ ] 用动态圆方树实现动态仙人掌By Isrothy
• [ ] 摊还分析
• [ ] 拟阵
• [ ] A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees
• [ ] Micali-Vazirani Algorithm
• [ ] Maximum Matchings via Glauber Dynamics
• [ ] Dial's Algorithm
• [ ] Gabow's Algorithm
• [ ] Nardelli-Proietti-Widmayer Algorithm
• [ ] Karger's Algorithm
• [ ] 最优化方法演算法筆記
• [ ] 迭代求解线性方程组
• [ ] 求根、不动点与特征点的关系演算法筆記
• [ ] Karmarkar's algorithm
• [ ] Mehrotra predictor-corrector method
• [ ] 维护双向加字符的字符串By 傅笙芳
• [ ] 排序网络
• [ ] 超现实数 方展鹏-《浅谈如何解决不平等博弈问题》
• [ ] Schreier-Sims 算法
• [ ] 万能欧几里得By Mr_Spade
• [ ] 量子算法
• [ ] +-1RMQ
• [ ] 信息熵
• [ ] 混合基FFT
• [ ] 树上后缀数组
• [ ] 启发式模拟退火（参见模拟退火一节）
• [ ] 收敛圆By 马同学
• [ ] 实数DFT/IDFT
• [ ] 误差函数erf的应用
• [ ] 分支定界法
• [ ] 高斯整数
• [ ] Stern-Brocot tree
• [ ] 格点计数By min-25
• [ ] 后缀平衡树
• [ ] Rainbow Tables
• [ ] 扩展欧拉定理在矩阵幂中的应用
• [ ] Bloom Filter
• [ ] 广义（有限域）DFT+数论算法
• [ ] 采样相关
• [ ] border_tree
• [ ] Perfect Hash Function
• [ ] 五边形数定理
• [ ] Link-Cut-MemphisBy Memphis
• [ ] Self-Adjusting Top trees（AAA树）

集训队论文/WC营员交流学习（省选后）

2019

• [ ] 模拟费用流 laofu

2018

• [x] 浅谈生成函数在掷骰子问题上的应用 杨懋龙
• [ ] 《后缀树结点数》命题报告及一类区间问题的优化 陈江伦
• [ ] 浅谈保序回归问题 高睿泉
• [x] 解决树上连通块问题的一些技巧和工具 任轩笛
• [ ] 一些特殊的数论函数求和问题 朱震霆
• [x] 浅谈Splay与Treap的性质及其应用 董炜隽
• [ ] 欧拉图相关的生成与计数问题探究 陈通

2017

• [ ] 关于数列递归式的一些研究 毛啸
• [ ] 基于线性代数的一般图匹配 杨家齐
• [ ] 浅谈信息学竞赛中的独立集问题 钟知闲
• [ ] 动态传递闭包问题的探究 孙耀峰
• [ ] 《A+B Problem》 命题报告 汪乐平
• [ ] 非常规大小分块算法初探 徐明宽
• [ ] 回文树及其应用 翁文涛

2016

• [x] 网络流的一些建模方法 姜志豪
• [ ] 浅谈线性规划与对偶问题 董克凡
• [ ] 浅谈无向图最小割问题的一些算法及应用 王文涛
• [x] 区间最值操作与历史最值问题 吉如一
• [x] 再探快速傅里叶变换 毛啸
• [ ] 从 Unknown 谈一类支持末尾插入删除的区间信息维护方法 罗哲正

2015

• [ ] 后缀自动机在字典树上的扩展 刘研绎
• [ ] 生成函数的运算与组合计数问题 金策
• [ ] 浅谈分块在一些在线问题中的应用 邹逍遥
• [ ] 仙人掌相关算法及其应用 王逸松
• [ ] DP的一些优化技巧 张恒捷
• [x] 集合幂级数的性质与应用及其快速算法 吕凯风

2014

• [ ] 对置换群有关算法的初步研究 岑若虚
• [ ] 浅谈维护多维数组的方法在数据结构题中的应用 梁泽宇
• [x] 线段树在一类分治问题上的应用 徐寅展
• [x] 根号算法——不只是分块 王悦同
• [x] 浅谈动态树的相关问题及简单拓展 黄志翱
• [x] 随机化算法在信息学竞赛中的应用 胡泽聪
• [ ] 寻找第 k 优解的几种方法 俞鼎力

2013

• [x] 浅谈分块思想在一类数据处理问题中的应用 罗剑桥
• [x] 搜索问题中的 meet in the middle 技巧 乔明达
• [x] 浅析信息学竞赛中概率论的基础与应用 胡渊鸣
• [x] 浅谈数据结构题的几个非经典解法 许昊然
• [x] 浅谈环状计数问题 高胜寒
• [x] 浅谈容斥原理 王迪
• [x] 浅谈一类分治算法 顾昱洲

Other

• [ ] 使用Vim或Emacs
• [x] 学习十指打字(目标：250cpm)
• [ ] 更换为Dvorak布局
• [ ] 整理引用的Bib与协议问题
• [ ] 合并并索引重复内容
• [ ] 学习Python3及其标准库用法
• [ ] 解题思路总结（省选前）
• [ ] 时间复杂度与正确性证明（大学）
• [ ] 移除不具有指导意义的代码
• [ ] 看看自己在那些题上是rank2

重构

• [x] SAM
• [ ] 带花树By rqy
• [ ] 三元环
• [ ] FWT
• [ ] CDF与PDF

退役后看到的新东西

• [ ] Hopcroft-Karp
• [ ] 无标号图编码
• [ ] 多项式计算 怎么还有CDQ分治和半在线卷积啊
• [ ] 在线卷积
• [ ] 双极定向
• [ ] 数论函数求和
• [ ] Barrett Reduction
• [ ] LA问题线性预处理O(1)查询
• [ ] zkw线段树上无修改rmq
• [ ] 三叶虫树 四毛子又是啥？
• [ ] 多元拉格朗日反演
• [ ] 质因数分解 怎么整上椭圆曲线了
• [ ] 莫队二次离线
• [ ] 任意模数二项卷积
• [ ] 多点求值优化