NOI 大纲:2021 vs. 2023

发布时间 2023-12-20 08:54:08作者: 陆留生信奥艺术

整体

正文采用文本格式,而不是原来模糊的图片,字号更大,空格更多。

J 组

  1. 明确了需要会使用 min,max,swap
  2. 加入了联合体。(毒瘤,至今我还没用过)
  3. “二叉树的孩子表示法”改为“二叉树的表示与存储”。
  4. 加入计数排序。(是的这事情我吐槽了多次)
  5. 加入了深搜广搜(第一次修订没想到你敢信?)
  6. 素数筛法埃氏筛法和线性筛法都要会。(虽然一般会线性筛人都会埃氏筛)
  7. 加入集合,可能在题目叙述时会方便一些。
  8. ”二叉搜索树的定义、构造及其遍历“中去除了遍历的要求。

S 组

  1. Linux 的相关操作变得更加概括,可能可以考察一些别的内容。
  2. container 和 iterator 的概念下放。
  3. 加入“算法模板库中的常用函数”,至于多常用算常用,并不明确。
  4. 将”有序队列“改成更常用的称呼(单调队列)。
  5. 新增“二叉堆”。感觉仍可用 priority_queue 代替,初赛可能会考。
  6. “基环树”上移到省选。
  7. 不要求掌握排列的哈希函数构造方法。(虽然实际上用字符串那一套啥事没有)。
  8. 明确了“离散化”是提高组考点。
  9. 去掉了“树形选择排序”。
  10. 去掉了“搜索对象的压缩存储”,不知道想干什么。
  11. 新增树的重心和直径、DFS 序和欧拉序。
  12. 明确树上差分、子树概念和树上倍增算法均为 S 组。
  13. 老考纲的”逆元“改成了”模运算意义下的逆元“(虽然还不够明确,应为”乘法逆元“)
  14. 新增多重集合概念。
  15. “向量的运算”从 NOI 级下放。

NOI 级

  1. 去掉 allocator, adapter, algorithm, functor 概念。
  2. 去掉“主席树”。
  3. 虚树被划为 10 级考点,NOI 及以下全部再见。
  4. 可持久化线段树为 8 级,可持久化其他东西为 9 级。
  5. 离线处理思想被划进 NOI 级。
  6. 有穷自动机全部定为 8 级,NFA 也可能考了。
  7. 明确 2-SAT 是 NOI 级考点。
  8. 去掉“二次互反律”。
  9. 去掉“卷积”。(请注意,卷积不止有 FFT,NTT)
  10. 随机变量的期望和方差划为 10 级考点。
  11. “Nim 博弈等”改成“Nim 博弈”,保证了没有其他博弈。