联赛前需要熟悉的东西

copy from KL59

图论

  1. 啥? spfa不是$O(n^2m)$的优秀算法吗?dijkstra才是正统的最短路。

  2. 缩点?tarjan没啥好说的。

  3. 割点。判一下dfn[x]>=low[v]或者是from==-1 and ch>1

  4. 差分约束?Spfa是什么我怎么没学过啊?【待复习】

  5. 二分图。匈牙利!

  6. 最小生成树。对不起我不会Prim

  7. 网络流。老年选手都不会打了【待复习】

  8. 拓扑排序。没啥好说

树形结构

  1. 树形dp。这个要难可以很难不会也没办法,注意转移的时候算size保证复杂度。

  2. 树剖。没啥好说,注意细节。

  3. 倍增。细节。

  4. 树上差分。不行就直接树剖。

数据结构

  1. 分块。这个真的要复习【待复习】

  2. 线段树。zkw不会打了,还是复习一下神奇用法吧。【待复习】

  3. 树状数组。(对不起我常数巨大。树状数组就只会模板,其他都线段树

  4. 平衡树。splay是个什么东西?我选择fhqtreap。

数论

  1. 筛素数。别打错了。
  2. 欧拉函数。容易忘【待复习】
  3. 乘法逆元。最后还是看一下吧【待复习】
  4. 高斯消元。不就是个模拟吗233

动态规划/字符串

  1. 背包。
  2. 状压DP。枚举子集S=S-1&T
  3. 区间DP。
  4. 最长公共子序列。还是再看看LIS的nlogn写法【待复习】
  5. 概率/期望。推方程
  6. kmp。还行,不要求next我就hash。不卡我就nlogn的hash
  7. trie树/AC自动机。搞一搞fail没啥好说的。
  8. hash。好东西。
  9. 斜率优化。这东西我已经忘的一干二净了。

其他

  1. dfs
  2. bfs
  3. 迭代加深
  4. 模拟
  5. 打表/找规律/卡常
  6. STL的各种使用

Leave a Reply

Your email address will not be published. Required fields are marked *