首页 > 代码库 > ·算法」 纲要

·算法」 纲要

基本

C/C++、STL(vectorsetmap、queue、string、algorithm)

枚举贪心递归、分治、递推、模拟

构造、位运算、常数优化

数据结构

队列、堆、、链表

排序(插入、冒泡、快速、归并、堆、桶、基数)

二分查找、散列表、并查集、哈夫曼树

排序二叉树、左偏树、平衡树(Splay/Treap/SBT)

树状数组线段树、归并树、划分树、主席树、树套树

树链剖分、动态树

1/2维RMQLCA(在线/离线)、稀疏表、字典树

字符串

KMP、扩展KMP

AC自动机

后缀树、后缀数组、后缀自动机

LCP随机化算法

最小表示法

搜索

DFS、BFS、剪枝、双向宽搜

迭代加深、A*、ID-A*

Dancing-links

爬山法、模拟退火、遗传算法

数学

进制转换、表达式求值

二分、三分

概率论、微积分

高精度(加减乘除模开方)

高精实数、分数

快速幂、矩阵、矩阵链乘

多项式求根、牛顿迭代

高斯消元解线性方程组

组合数学、排列组合计数

容斥原理、抽屉原理、mobius反演

置换群、burnside 引理、Polya定理、母函数

卡特兰数、斯特林数

傅立叶变换(大数乘法)

半平面交解二元线性规划、单纯形法解线性规划

约瑟夫问题

0/1分数规划

数论

GCD、扩展欧几里德

筛法求素数、素数判定

同余方程、中国剩余定理

大素数测试、分解

欧拉函数、积性函数、法兰数列

逆元、离散对数

图论

基本概念(DFS生成树上边,桥,割点,割,双连通分量)

图的表示(矩阵、邻接表)

最短路(Dijkstra(+heap)、Floyd、Bellmen-ford、Spfa)、传递闭包

最小生成树

强联通分量(+缩点)

拓扑排序

桥、边双连通分量及性质

割点、点双连通分量

度限制生成树、次小生成树、最优比例生成树

最小树形图

次短路(Dijkstra)、K短路(A*)

差分约束系统

2-SAT

欧拉路径(回路)、汉密尔顿路(回路)

网络流(SAP、Dinic)

最大流最小割、平面图最小割、全局最小割Stoer-Wagner算法

最小费用最大流

有流量上下界的网络流(费用流)

无源汇的网络流

二分图匹配、二分图最大权匹配

任意图匹配(带花树)

最大权闭合子图、最大密度子图

最大团、最大独立集

计算几何

基本操作:

  叉积、点积

  向量平移、旋转

  线段(直线、射线)相交的判断、求交点

  点、线段、直线、平面关系、距离

  点在多边形内/外/上

  多边形周长、面积

二维凸包

最近点对、最近圆对

旋转卡壳

        计算距离:凸多边形直径、形宽,凸多边形间的最大、最小距离

        外界矩形:最小周长、最小面积外界矩形

        三角剖分:洋葱、螺旋、四边形剖分

        凸多边形属性:凸包合并、找公切线、临界切线、凸多边形相交、凸多边形矢量和

        最薄截面:最薄横截带

三角形

球面距离

三维几何基本操作

        向量平移、旋转

        点、线、面

三维凸包

点集的最小覆盖圆

最大空心矩形

圆的面积交/并

圆与圆的位置关系

圆与线段、多边形的关系、面积

半平面交

自适应simpson公式

steiner生成树

动态规划

记忆化搜索

最长公共子序列

最长上升序列

背包九讲(0/1、完全、依赖、分组、泛化物品)

四边形不等式优化、斜率优化、单调队列(1D\1D)

数据结构优化(线段树优化、堆优化、左偏树优化)

树形DP、自动机DP

数位DP、状态压缩DP、插头DP、广义插头(最小表示)

博弈论

Bash Game、Wythoff Game

NIM、SG函数

搜索、极大极小搜索

无向图删边博弈

其他

历法、日期汉诺塔

 

离散化

找规律

打表