/xcpc-algorithm-templates

XCPC/ICPC/CCPC 算法模板

Primary LanguageC++MIT LicenseMIT

简介

在本科期间,本人获得了XCPC金奖共计8枚,包括EC Final金奖和CCPC Final金奖,区域赛最好成绩为2020CCPC长春站的季军。 此外还获得过CCSP 金奖,CCCC 一等奖,华为嵌入式软件大赛总决赛算法组 冠军,华为算法大赛高校组 冠军,ICPC 2023 Online Challenge powered by Huawei 一等奖(**区第一名,总排名第五)。

目前本人已退役,并将自己的算法模板整理如下,重点是数据结构和字符串,涉及的数论和计算几何较少(队友负责)。

本算法库持续更新中...

如果你有好的算法模板想加入进来,或者觉得此算法库有bug,欢迎提出pull requests。

目录

  • 图论
    • 确定有限状态自动机最小化
    • 拓扑排序
    • 欧拉回路
    • 最小生成树
    • Dijkstra算法
    • SPFA算法
    • 一般图最大权匹配
    • 有向图的传递闭包
    • 最小树形图
    • 支配树
  • 树算法
    • 限定距离的子树问题
    • 树的欧拉序
    • 倍增求LCA
    • 点分治
    • 动态点分治
    • 快速求树中与结点x距离不超过k的点权和
    • 动态维护树中白色结点的最长距离
    • 虚树
    • O(1)-LCA
  • 基础算法
    • Java快速读入
    • C++快速读入
    • C++光速读入(交互版)
    • C++17 万能输出
    • C++20 万能输出
    • RMQ算法
    • 哈希表
    • 哈希值组合
    • 基数排序
    • 快速离散化
    • 带删除的优先队列
    • 排列组合枚举
    • 动态维护连续相同数字区间
    • 二分查找
    • 计时器
    • 动态数组
  • 匹配算法
    • 匈牙利算法
    • KM算法
    • 带花树算法
  • 高精度
    • 大整数类
    • 分数类
    • 高精度定点数
  • 动态规划
    • 斯坦纳树(点权)
    • 斯坦纳树(边权)
    • 插头DP
    • 最长上升子序列
  • 莫队算法
    • 莫队算法
    • 回滚莫队
    • 带修改莫队
  • 数据结构
    • 可修改优先队列
    • AVL Tree
    • TopTree
    • 可持久化数组
    • 四分树
    • Treap
    • link-cut-tree
    • link-cut-tree(指针)
    • link-cut-tree(边权)
    • link-cut-tree(维护子树)
    • 可持久化Treap
    • 树链剖分
    • 树链剖分求LCA和距离
    • 树状数组
    • 李超线段树
    • 整数集合
    • 可持久化整数集合
    • 线段树
    • 动态开点线段树
    • 主席树
    • 动态主席树
    • 动态开点线段树(单点加-区间求和-合并)
    • 可持久化线段树
    • 线段树(历史最大值)
    • zkw线段树(单点加-区间加-单点查询-区间求和)
    • SplayTree
    • 可持久化并查集
    • KD-Tree
    • Euler-Tour-Tree
    • rope
    • pb-ds平衡树
  • 数学算法
    • SG函数
    • 自适应辛普森积分
    • 高斯消元
    • 稀疏矩阵的高斯消元
    • 求解异或方程组
    • 矩阵与状态转移
    • 递推式求解
    • 快速傅里叶变换
    • 快速幂运算
    • 莫比乌斯反演
    • 逆元
    • 欧拉函数
    • 线性筛素数
    • 三分求极值
    • 多项式拟合(辛普森积分)
    • 多项式拟合(泰勒展开)
    • 雅可比方法
    • 矩阵求逆
    • 牛顿迭代求非线性方程组
    • QR迭代
    • 行列式计算
    • 二元一次不定方程
    • 线性规划
  • 网络流
    • Dinic
    • ISAP
    • HLPP
    • MCMF-spfa
    • MCMF-dijkstra
  • 字符串算法
    • 后缀树
    • 扩展KMP
    • AC自动机
    • KMP算法
    • Manacher算法
    • 后缀数组
    • 后缀自动机
    • 回文自动机
    • 回文串Border
    • 双端回文自动机
    • 非势能分析回文自动机
    • 序列自动机
    • hash
    • LCT维护隐式后缀树
    • 区间本质不同子串个数
    • Lyndon分解
    • 后缀平衡树
    • 模糊匹配
    • 基于后缀自动机构建后缀树
  • 人工智能
    • 主成分分析
    • Adam算法
    • Dyna-Q
    • kmeans聚类