NOIP知识点总结

  1. 1 最重要
  2. 2 次重要
  3. 3 比较重要
  4. 4 注意

整理一下,需要注意的东西

1 最重要

  1. 模拟
  2. 贪心
    • 想改变最大值时的条件
    • 数据大的时候
  3. 搜索+剪枝
  4. DP(各种背包、记忆化)
  • 注意边界、数组下标、初始化
  • 第一题不要想DP
  1. 数论(gcd、exgcd、筛法求素数、φ)
  2. 字符串
  • HASH ①自然溢出/mod 100,000,007 ②strlen(a) 注意用变量固定
  • kmp 注意边界
  • 字典树马拉车

2 次重要

  1. 二分
  • 注意边界、单调性、有时候需要 离散化
  1. 快速幂
  2. 并查集、带权并查集
  3. 优先队列 priority_queue qi;
  4. 排序(拓扑排序
  5. 最短路
  • SPFA 判负环
  • Dijkstra 优先队列 + 结构体(权值+编号)
  1. 最小生成树(Kruskal、Prim)+ 各种(如LCA)

3 比较重要

  1. 线段树、树状数组(可以求逆序对)(区间最值)、ST(RMB RMQ问题)
  2. STL(如map、set、vector、queue、heap等)
  • set用迭代器遍历的时候不能删元素,因为会变
  1. 强连通分量(tarjan找环、缩点)
  2. 高精(压位高精)(加减乘)
  3. LCA(可以暴力往上跳)
  4. 二分图(最大流/匈牙利算法
  5. 矩阵乘法
  6. 暴力+优化(乱搞)

4 注意

  1. 对拍
  2. cstring 千万别忘写
  3. 时间复杂度
  • logn 二分、gcd、exgcd
  • n 贪心、模拟、并查集、单调队列、kmp、筛法.
  • nlogn 最短路、sort、线段树、树状数组、st
  1. 系统函数