noip知识点

动态规划

  • 线性dp
  • 区间dp
  • 树形dp
  • 线段树优化
  • 前缀和优化
  • 单调队列优化
  • 滚动数组优化内存
  • (状压dp,数位dp,斜率优化,矩阵乘法加速)

数据结构

  • 队列
  • 双向链表(约瑟夫环)
  • 树状数组
  • 线段树
  • (树剖,主席树,平衡树,树套树,kd-tree,动态树)

图论

  • MST
  • 最短路
  • Tarjan(强联通分量,割点割边)
  • 并查集
  • 拓扑排序
  • 2-sat
  • 差分约束
  • 二分图(判定是否是二分图,二分图最大匹配)
  • (网络流)

字符串

  • hash
  • KMP
  • trie
  • (后缀数组,AC自动机)

数论

  • gcd,扩展gcd
  • 最简单的排列组合C[i][j]=C[i-1][j]+C[i-1][j-1]
  • 筛质数
  • (欧拉函数,mobius反演,FFT)

搜索

  • 对拍的搜索
  • 数据生成器
  • 可行性剪枝
  • 最优性剪枝

其他

  • 倍增
  • LCA
  • ST表
  • 前缀和(区间查询,无修改)
  • 差分(区间修改,所有修改完后再查询)
显示 Gitment 评论