Skip to content

OI代码仓库、复习笔记、代码模板、本地Judger

Notifications You must be signed in to change notification settings

dtcxzyw/OI-Source

Repository files navigation

GitHub code size in bytes

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

该仓库包括:

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

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

高考加油吧。

Review

博弈论

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

网络流

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

数据结构

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

数学

数论

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

集合论/群论

  • 置换 Polya定理
  • 容斥

组合数学

  • Catalan
  • Stirling
  • lucas/exLucas

多项式

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

线性代数

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

其他

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

动态规划

  • 背包
  • 数位动规
  • 插头dp
  • LCIS

dp优化

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

图论

  • LCA
  • 树链剖分(重链剖分/长链剖分)
  • 树的直径
  • 点分治
  • 虚树
  • purfer序列
  • dsu on tree

最短路

  • SPFA
  • Dijskra
  • Floyd
  • 差分约束
  • k短路

生成树

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

其他

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

字符串

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

计算几何

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

最优化问题

  • 爬山法
  • 模拟退火(分块模拟退火)
  • 遗传算法
  • A*算法
  • 梯度下降
  • 01分数规划

思想/技巧

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

卡常

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

理论

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

Advance

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

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

2017

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

2016

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

2015

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

2014

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

2013

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

Other

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

重构

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

退役后看到的新东西