中小学信息学指南（NOIP及以下难度）

Feng Zhou, 2022-2

介绍

本网上讲义编写目的有这样几条：

• 作为信息学CSP-J/S, NOIP, USACO Silver/Gold难度参赛的查漏补缺依据，面向小学高年级到高一年龄段。方便不同学习经历和状态的选手，来快速定位薄弱知识并快速补齐。
• 通过网站这样方便更新的方式维护，保持对学习与备考新信息的同步跟踪，并链接高质量的网上资源（比如题库）。

文章列表

• 基础
  • 学习规划与参考资料
  • 基本环境、技能与编程语言
  • 问题类型与知识点范围
• 基础算法
  • 复杂度 - 大O记号
  • 倍增 - 将线性运算转化成对数运算
  • 搜索与模拟
  • 离散化
• 数据结构
  • 并查集 - 处理不交集的合并和查询
  • 区间问题相关数据结构
    • 前缀和与差分 - 解决区间问题的基本方法
    • 线段树 - 维护区间信息
    • 树状数组(可选) - 单点/区域修改、单点/区域查询
    • ST表(可选) - 可重复贡献问题
  • 单调队列 - 复用具有单调性的计算结果
  • 单调栈 - 类似单调队列
  • 哈夫曼树 - 构造最短带权路径长度二叉树
• 图论
  • 单源最短路
    • Dijkstra - 一点到所有点的最短路（非负权）
    • SPFA和Bellman-Ford - 一点到所有点的最短路（可能有负权）
    • 差分约束 Differential Constraints - 转化成SPFA看是否有负环
  • 所有点间最短路
    • Floyd-Warshall - 所有点之间的最短路
  • 生成树
    • 最小生成树
    • 最小生成树的唯一性
    • 最小瓶颈树
  • 树上问题
    • 树的重心
    • LCA最低公共祖先 - 通过倍增快速求解
    • 树上差分
  • 网络流
    • 最大流
  • 拓扑排序
  • 强连通分量 Strongly Connected Components
• DP
  • 动态规划基础
  • 背包DP
  • 序列和环上的动态规划
  • 树形DP
  • 多维动态规划
  • 输出方案的动态规划
• 数学
  • 数论
    • 最大公约数 gcd
• 计算几何
  • 扫描线

• 杂项

  • The C++ Standard Template Library (STL) by geeksforgeeks
    • 一些用得较多的STL类包括：vector, queue/deque, priority_queue, set/multiset, map/unordered_map
  • 位操作等C++技巧
  • 快速输入输出
  • 链式前向星 - 优化的图表示
  • Meet-in-the-middle

• 其它资源

  • 洛谷题单广场
  • Studying Father的NOI题单 (2020)
  • 洛谷上的USACO题目，其中training部分来自于USACO Training