NOIP知识点总结

OI&ACM, 总结
  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. 系统函数