NOIP 专题 · 全国青少年信息学奥林匹克联赛（提高组）
NOIP 提高组
省级联赛
NOIP 由 CCF 主办，各省独立评奖，一般每年 11 月举行。它题量大、难度高、时间紧，一场比赛就是四个小时的高强度输出。对大多数学生来说，NOIP 是「检验平时积累」的舞台，而不是「临时抱佛脚」能解决的事。本专题按六大模块拆解考点，并给出从 CSP-S 到 NOIP 的完整备赛路径。
一、赛事概览与参赛规则
| 项目 | 说明 |
|---|---|
| 全称 | 全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces） |
| 主办方 | 中国计算机学会（CCF），各省赛区承办 |
| 面向对象 | 高中及初中生，编程与算法基础扎实者 |
| 编程语言 | C++（ 本站聚焦 C++ 方向） |
| 举行时间 | 一般每年 11 月举行（具体以 CCF 当年公告为准） |
| 评奖方式 | 各省独立评奖，省内划定一等奖 / 二等奖分数线 |
| 晋级路径 | 部分省份 NOIP 成绩优异者可获得后续省选 / 国赛资格 |
NOIP 与 CSP-S 的关键差异
CSP-S 第二轮通常 3 小时 4 道题；NOIP 往往时间更紧、题量更多，且几乎不考纯概念，全部是算法设计。没有长期积累的学生，往往第一题能拿分、后面直接崩盘。
二、网络流入门
网络流是 NOIP 的「招牌考点」，出现频率极高，但复杂度相对可控，是性价比很高的一块。
| 模型 | 解决的问题 | 关键转化 |
|---|---|---|
| 最大流 | 带容量限制的最优运输/分配 | 拆点限制容量，把分配问题建成图 |
| 最小割 | 与最大流对偶，常用于「删最少边使某两点不连通」 | 答案 = 最大流；建图时注意拆点与 INF 边 |
| 费用流 | 带费用的最优方案，如「每单位流量有不同成本」 | 反向边费用取负，用 SPFA 增广 |
| 最大权闭合图 | 有依赖关系的选择问题 | 依赖关系用 INF 边连向被依赖方，再求最大权闭合 |
| 上下界可行流 | 流量有最小 / 最大限制 | 加边转化后跑一次流判断可行性 |
Dinic 最大流（模板，NOIP 常用）
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010;
int n, m, S, T;
struct Edge {
int to, next, cap;
} edges[M];
int head[N], idx = 0;
int level[N], cur[N];
void addEdge(int u, int v, int cap) {
edges[idx] = {v, head[u], cap};
head[u] = idx++;
}
bool bfs() {
memset(level, -1, sizeof(level));
queue<int> q;
level[S] = 0; q.push(S);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (edges[i].cap > 0 && level[v] == -1) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[T] != -1;
}
int dfs(int u, int flow) {
if (u == T) return flow;
for (int &i = cur[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (edges[i].cap > 0 && level[v] == level[u] + 1) {
int pushed = dfs(v, min(flow, edges[i].cap));
if (pushed > 0) {
edges[i].cap -= pushed;
edges[i ^ 1].cap += pushed; // 反向边（i^1 配对）
return pushed;
}
}
}
return 0;
}
int dinic(int s, int t) {
S = s; T = t;
int ans = 0;
while (bfs()) {
memcpy(cur, head, sizeof(head));
int f;
while ((f = dfs(S, 1e9)) > 0) ans += f;
}
return ans;
}
int main() {
fill(head, head + N, -1);
cin >> n >> m >> S >> T;
for (int i = 1; i <= m; i++) {
int u, v, cap; cin >> u >> v >> cap;
addEdge(u, v, cap);
addEdge(v, u, 0); // 必须加反向边
}
cout << dinic(S, T) << '\n';
return 0;
}网络流三大坑
- 忘记加反向边——用
edges[i ^ 1]配对时，加边函数必须一次加两条（容量一正一零）。 - INF 设置不当：拆点做最小割时 INF 太小会误割，INF 要大于可能的最大流量。
- 递归层数：网络流递归深度大，节点上万时可能要改成非递归写法。
三、进阶数据结构
| 数据结构 | 解决什么 | 备注 |
|---|---|---|
| 树链剖分 | 路径查询 / 路径修改 + 线段树，支持任意树上操作 | NOIP 高频，建树和重链剖分要熟练 |
| 可持久化线段树 | 区间第 K 小、区间不同数个数、主席树经典应用 | 只需会写「插入产生新版本」即可 |
| 平衡树 | 动态第 K 大、操作序列的最值 | 了解 Treap 旋转思想即可，Splay 偏难 |
| 扫描线 | 二维偏序、矩形面积 / 周长统计 | 线段树 + 离散化，套路题居多 |
四、字符串进阶
相比 CSP-S 只多出后缀数组和后缀自动机两块，这两块理解成本高，但一旦模板化就是稳定得分点。
| 算法 | 应用 |
|---|---|
| 后缀数组 | 求最长重复子串、子串去重比较、LCP / RMQ 配合解 LCP 查询 |
| 后缀自动机 | 不同的子串个数、字符串的最小表示、复杂字符串统计 |
| 字符串哈希进阶 | 用双哈希把字符串比较降到 O(1)，与二分结合做最长公共前缀 |
学习建议建议：先把后缀数组的倍增法吃透，后缀自动机可作为进阶选学。NOIP 里字符串题常和哈希、二分组合出现，掌握双哈希 + 二分往往比学 SAM 更划算。
五、DP 与图论优化
| 优化手段 | 适用场景 | 核心思想 |
|---|---|---|
| 斜率优化 | DP 转移可化为 max/min 的一次函数 | 用单调队列维护凸包，均摊 O(1) |
| 四边形不等式 | 区间划分类 DP（石子合并、括号匹配） | 限制决策单调性，O(n²) 优化到 O(n log n) 或 O(n²) |
| 插头 DP | 网格 / 棋盘类路径计数与最小代价 | 用二进制或括号序列记录轮廓线连通性 |
| DP 套 DP | 多个独立子问题共享 DP 结构 | 把一个 DP 当作另一个 DP 的转移函数 |
| 最短路进阶 | 分治最短路、矩阵快速幂优化最短路 | 适用于节点数小、边权特殊的情形 |
现实建议
这些优化 NOIP 会出现，但往往不是「必须做出来才能得分」的题。基础 DP / 最短路写对，答案已经拿了大头；优化题放最后，用「能推则推、推不出就拿暴力分」的策略。不要因为死磕优化题而丢掉前面的基础分。
六、数学进阶
| 知识点 | 典型应用 |
|---|---|
| 莫比乌斯反演 | 整除关系计数、GCD 相关求和，是 NOIP 数论题的主力工具 |
| 生成函数 | 计数与组合问题的系统性求解，进阶选学 |
| FFT / NTT | 大整数乘法、多项式卷积 |
| 组合数学进阶 | 容斥、组合数取模、卡特兰数、错位排列等 |
提示莫比乌斯反演是这四块里最值得优先攻的——它的套路相对固定，学会了在多道题里都能复用。FFT 和生成函数投入产出比偏低，除非已有扎实基础，否则可以先放一放。
七、计算几何基础
| 知识点 | 说明 |
|---|---|
| 向量与叉积 | 判断点在多边形内、线段相交的基础工具 |
| 凸包 | Andrew 算法 O(n log n) 求凸包，配合旋转卡壳解决直径 / 最远点对 |
| 面积公式 | Shoelace 公式求多边形面积；点在多边形内判定（射线法 / 叉积法） |
Andrew 凸包（模板，O(n log n)）
#include <bits/stdc++.h>
using namespace std;
struct Pt {
double x, y;
bool operator < (const Pt& o) const {
return x == o.x ? y < o.y : x < o.x;
}
};
double cross(const Pt& a, const Pt& b, const Pt& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
vector<Pt> convexHull(vector<Pt> pts) {
sort(pts.begin(), pts.end());
int n = pts.size();
if (n <= 1) return pts;
vector<Pt> hull(2 * n);
int k = 0;
// 下凸壳
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(hull[k - 2], hull[k - 1], pts[i]) <= 0) k--;
hull[k++] = pts[i];
}
// 上凸壳
int t = k + 1;
for (int i = n - 2; i >= 0; i--) {
while (k >= t && cross(hull[k - 2], hull[k - 1], pts[i]) <= 0) k--;
hull[k++] = pts[i];
}
hull.resize(k - 1); // 首尾点重合，去掉一个
return hull;
}八、备赛路径与能力自测
从 CSP-S 到 NOIP 的四个阶段
- 补齐前置：完整学完 CSP-S 专题 全部模块，确保树状数组、线段树、最短路、Tarjan、基础 DP 能独立写出。这一步不能省。
- 主攻网络流：最大流 → 最小割 → 费用流 → 最大权闭合图，每类至少 5 题，网络流是 NOIP 最稳的得分点。
- 补进阶结构与优化：树链剖分、主席树、扫描线；DP 优化按「斜率 → 四边形 → 插头」的顺序推进。
- 数学与几何选学：优先莫比乌斯反演，其次凸包 + 旋转卡壳；FFT / 生成函数按需选学。
- 限时实战：找历年真题按真实考场时间完整模拟至少 5 套，训练「读题 → 建模 → 实现 → 检查」的完整节奏。
能力自测（能默写模板才算过关）
| 序号 | 自测项 | 掌握度 |
|---|---|---|
| 1 | Dinic 最大流模板，能解释当前弧优化的作用 | □ 熟练 □ 看模板 □ 没思路 |
| 2 | 把「最少删边使两点不连通」转成最小割建模 | □ 熟练 □ 看模板 □ 没思路 |
| 3 | 费用流求带成本的最优分配 | □ 熟练 □ 看模板 □ 没思路 |
| 4 | 树链剖分 + 线段树支持路径修改查询 | □ 熟练 □ 看模板 □ 没思路 |
| 5 | 莫比乌斯反演解决整除关系计数 | □ 熟练 □ 看模板 □ 没思路 |
| 6 | Andrew 凸包，能用它求面积和最远点对 | □ 熟练 □ 看模板 □ 没思路 |
| 7 | 斜率优化：把 O(n²) DP 压到 O(n) | □ 熟练 □ 看模板 □ 没思路 |
| 8 | 能独立分析一道 NOIP 题的模型与复杂度 | □ 熟练 □ 看模板 □ 没思路 |
九、赛场失分点与策略
NOIP 赛场上最可惜的丢分
- 读题太慢：四小时十几道题，第一遍读题务必留下标记，先做有把握的。
- 卡在一道题上死磕：单题超过 40 分钟没进展就果断跳过，回头再攻。会的题永远比不会的多。
- 复杂度没估：n = 1e5 却写 O(n²)，写完才发现是 TLE。写代码前先算复杂度。
- 忘开 long long：乘法溢出是 NOIP 的经典送命点。
- 递归爆栈：链状结构深度到 1e5，递归会爆栈，改迭代。
- 最后一小时没检查：至少留 15 分钟通读代码，看有没有笔误、数组开小、忘多测。
一句话总结
NOIP 拼的是基础模型的熟练度 + 建模速度 + 稳定的临场发挥。与其追求冷僻算法的覆盖，不如把树状数组、线段树、网络流、Tarjan、基础 DP 这几块练到闭着眼睛都能写出来。相关应试细节可回看 20 机考应对与坑点。
十、NOIP 配套模拟题
下面 20 道题按单选 → 程序阅读 → 编程三类组织，覆盖网络流、树剖、DP 优化、 莫比乌斯、计算几何等进阶考点。题库为教学自编，用于配套练习与自测，不是官方历年真题。