OI省选算法汇总

2014年11月24日10,31729

简单列了一点

1.1 基本数据结构

1. 数组

2. 链表,双向链表

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

4. 栈,单调栈

1.2 中级数据结构

1. 堆

2. 并查集与带权并查集

3. hash 表

    自然溢出

    双hash

1.3 高级数据结构

1. 树状数组

2. 线段树,线段树合并

3. 平衡树

    Treap 随机平衡二叉树

    Splay 伸展树

    * Scapegoat Tree 替罪羊树

4. 块状数组,块状链表

5.* 树套树

    线段树套线段树

    线段树套平衡树

    * 平衡树套线段树

6.可并堆

    左偏树

    *配对堆

7. *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编码

7. 拓扑排序

8. 欧拉图

9. 二分图

    *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.模拟与贪心

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

3. 分治,CDQ分治

4. 高精度

5. 离线

6. ST表

1.13 STL

1. map

2. priority_queue

3. set

4. bitset

5. rope

1.14 非常见算法

1. *朱刘算法

2. *弦图与区间图

  • 装在盒子里的炸鸡块2014年11月24日 下午9:51 回复

    坐到前排了….感谢分享> <

    #1  
  • fa...x@163.com2014年11月25日 上午10:57 回复

    orz

    #2  
  • -D-Z-N-2014年11月25日 下午2:06 回复

    o(* ̄▽ ̄*)ブ 学长好厉害的说

    #3  
  • 永远14岁的创世sama2014年11月26日 下午6:37 回复

    卧槽我的数据结构有好多都不会。。。
    就会普通的栈队列HASH并查集数组线段树外带一个SBT

    #4  
  • […] OI省选算法汇总 […]

    #5  
  • huanghongxun2015年9月9日 下午5:39 回复

    虽然全部算法都写得了代码,然而并不会做题

    #6  
    • 陆葳蕤pastos2015年9月10日 下午7:13 回复

      %%%%%%%

      #61
      • Luka2015年9月12日 下午2:40 回复

        控QAQ

        #62
        • 陆葳蕤pastos2015年9月13日 下午6:27 回复

          卧槽……你是从哪儿冒出来的

          #63
          • Luka2015年9月21日 下午4:52

            hahhh蛤蟆控

            #64
    • hyl2016年4月26日 下午5:37 回复

      orz

      #61
  • 凹凸凹凸2015年9月21日 下午6:47 回复

    为毛没有k短路,昨天考的被虐哭QAQ

    #7  
    • hzwer2015年9月21日 下午7:24 回复

      k短路是用A*算法吧

      #71
      • 凹凸凹凸2015年9月21日 下午7:25 回复

        是啊,正在学,有人打dfs + 二分答案都过了。。。

        #72
        • 匿名2015年9月22日 下午2:43 回复

          你是哪个。。。

          #73
          • 凹凸凹凸2015年9月22日 下午4:38

            饿,你又是那个,认识我的人看头像就知道了吧。。。

            #74
          • 欣欣2015年9月22日 下午8:36

            我认识你!!我是欣欣!!

            #74
          • 凹凸凹凸2015年9月22日 下午9:22

            我不认识农民。。。

            #74
          • hzy2015年9月23日 下午2:23

            我是梅老师,我来抓堕了

            #74
  • szy0422016年1月11日 下午7:25 回复

    黄学长,现在还会多什么新的算法吗。。。

    #8  
    • hzwer2016年1月11日 下午7:54 回复
      admin

      这些是两年前的学长留下来的,我修改了一点,应该这两三年不会变化太大
      当然上面列的肯定没那么完整

      #81
  • a2016年2月4日 上午10:52 回复

    请问打*是什么意思?

    #9  
    • hzwer2016年2月4日 下午7:05 回复
      admin

      选学。。。

      #91
  • will2016年2月5日 下午11:07 回复

    orz%%%

    #10  
  • […] 声明:算法分类方式与列举顺序借鉴于hzwer同学的《OI省选算法汇总》。 […]

    #11  
  • […] hzwer,《OI省选算法汇总》。 […]

    #12  
  • […] 考点见省选算法汇总 […]

    #13  
  • […] 注:本文转自:http://hzwer.com/1234.html […]

    #14  
  • 填坑计划 | 远航休息栈2017年3月15日 下午3:52 回复

    […] 转载自黄学长博客 […]

    #15