前路漫长。[转载]OI省选算法汇总。

重整一下前而学的东西

简单列了几许

实则我呢无知晓自己写的物是啊东西,简单的排列一下吧

1.1 基本数据结构

在押了从未亮的

FFT(单位到底是什么不好啊。。。)

  1. 数组

  2. 链表,双向链表

  3. 列,单调队列,双端队列

  4. 栈,单调栈

 

1.2 中级数据结构

辅助类

Vim

Latex

Markdown

geogebra

 

  1. 并查集与带权并查集

  2. hash 表

    本来溢起

    双hash

数据结构/算法

单调栈,单调队列,双端队列

线段树

  zkw线段树

  二维线段树/树状数组

  动态开节点线段树

  李超线段树

  线段树合并

平衡树

  Splay

  Treap

  FHQ Treap

  SBT

  AVL

  替罪羊树

  红黑树

  斜堆

  左偏树

  随机堆

  二项堆

  斐波那契堆

  Pairing堆

唯独持久化

  线段树

  数组

  平衡树

分块

  分块

  块状数组

  块写链表

树上算法

  树链剖分

  K-D Tree

  四分树

  树的分治算法(点分治,边分治,*动态?树分治)

  动态树 (LCT,*树分块)

  虚树

  *prufer编码

连查集/带权并查集

字符串

  KMP 

  BM

  Sunday

  Trie树

  AC自动机

  Manacher

  后缀数组

  后缀自动机

  后缀树

图论

  割点,割边

  蹩脚短路,k短路,最缺少里程计数

  kruskal重构树

  欧拉图

  二分图/KM/匈牙利

网络流

  最大流

  最小割

  费用流

  分数规划

动态规划

  斯坦纳树

  斜率优化

  四度形不等式优化

  前缀和优化

  1D1D优化

  插头DP

  DP套DP

  数位DP

  树形DP

莫队

  树上莫队

  在线莫队

  待修改莫队

  树上待修改莫队

模拟退火

登山算法

肆意增量法

三维偏序

CDQ分治

赤刘算法

弦图和区间图

1.3 高级数据结构

数学

参见一本通

 

 

  1. 树状数组

  2. 丝段树,线段树合并

  3. 平衡树

    Treap 随机平衡二叉树

    Splay 伸展树

    ~Scapegoat Tree 替罪羊树

  4. 片状数组,块写链表

便模板

 

#include<cstdio>
const int MAXN=1e6+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int sum=0,f=1;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=nc();}
    while(c>='0'&&c<='9')sum=sum*10+c-48,c=nc();
    return sum*f;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int a=read(),b=read();
    printf("%d",a+b);
    return 0;
}

 

5.~ 树套树

线段树套线段树

线段树套平衡树

~平衡树套线段树

6.可并堆

左偏树

~配对堆
  1. ~KDtree,~四分树

1.4 可持久化数据结构

  1. 不过持久化线段树

    主席树

  2. ~ 可持久化平衡树

  3. ~ 可持久化块状数组

1.5 字符串相关算法和数据结构

  1. KMP

  2. AC 自动机

  3. 继缀数组

  4. ~后缀树

  5. ~后缝自动机

  6. 字典树 Trie

  7. manacher

1.6 图论相关

  1. 尽小生成树

    prim

    kruskal

  2. 最短路,次短路,K短路

    spfa

    dijkstra

    floyd

  3. 祈求的通

    连片分量

    割点,割边

  4. 网络流

    最大流

    最小割

    费用流

    分数规划

  5. 树相关

    树上倍增,公共祖先

    树链剖分

    铸就之分治算法(点分治,边分治,~动态?树分治)

    动态树 (LCT,~树分块)

    虚树

    ~prufer编码

  6. 拓扑排序

  7. 欧拉图

  8. 二分图

    ~KM算法

    匈牙利算法

1.7 数学相关

  1. (扩展)欧几里得算法,筛法,快速幂

    斐蜀定律

    双重相减损术

  2. 欧拉函数与~降幂大法

  3. 费马小定理

  4. 排列组合

    lucas定理

  5. 乘法逆元

  6. 矩阵乘法

  7. 数学期望与概率

  8. 博弈论

    sg函数

    树上删边游戏

  9. ~拉格朗日乘子法

  10. 中华剩余定理

  11. 线性规划暨网络流

  12. 单纯型线性规划

  13. 辛普森积分

  14. 范线性方程组

  15. 容斥原理及莫比乌斯反演

  16. 置换群

  17. 很快傅里叶变换

  18. ~大步小步法(BSGS),扩展BSGS

1.8 动态规划

  1. 诚如,背包,状压,区间,环形,树形,数位动态规划

    记忆化搜索

    斯坦纳树

    背包九开腔

  2. 斜率优化及~ 四限形不等式优化

  3. 环 + 外望树上的动态规划

  4. ~插头动态规划

1.9 计算几何

  1. 计量几哪基础

  2. 其三维计算几哪初步

  3. ~梯形剖分与~三角形剖分

  4. 转卡壳

  5. 一半面及

  6. pick定理

  7. 扫描线

1.10 搜索相关

  1. bfs,dfs

  2. A~ 算法

  3. 迭代加重搜索,双向广搜

1.11 特殊算法

  1. 莫队算法,~树上莫队

  2. 模拟退火

  3. 登山算法

  4. 轻易增量法

1.12 其它要工具及办法

1.学和贪心

  1. 二分,三分法(求偏导)

  2. 分治,CDQ分治

  3. 高精度

  4. 离线

  5. ST表

1.13 STL

  1. map

  2. priority_queue

  3. set

  4. bitset

  5. rope

1.14 非常见算法

  1. ~朱刘算法

  2. ~弦图与区间图

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注