竞赛编程术语词汇表

本词汇表定义了贯穿全书及竞赛编程领域常用的 35+ 个核心术语。遇到不熟悉的术语时，请先在这里查阅。

A

算法（Algorithm） 解决问题的分步骤过程。算法必须：正确（给出正确答案）、有限（最终终止）、确定（每步无歧义）。示例：二分查找、BFS、归并排序。

邻接表（Adjacency List） 图的一种表示方式：每个顶点存储其邻居列表。空间：O(V + E)。竞赛编程中的标准表示方式。

邻接矩阵（Adjacency Matrix） 二维数组，matrix[u][v] = 1 表示 u 到 v 有边。空间：O(V²)。仅在 V ≤ 1000 的稠密图中使用。

摊还时间（Amortized Time） 一系列操作的每次操作平均时间。示例：vector::push_back 的摊还时间为 O(1)，即使偶尔的扩容需要 O(N)。

B

边界条件（Base Case） 递归和 DP 中，具有已知答案的最简子问题（无需进一步递归）。示例：fib(0) = 0，fib(1) = 1。

BFS（广度优先搜索，Breadth-First Search） 逐层探索节点的图遍历（先遍历所有距离为 1 的节点，再遍历距离为 2 的节点……）。使用队列。在无权图中保证最短路径。时间复杂度：O(V + E)。

大 O 表示法（Big-O Notation） 描述算法时间或空间增长上界的数学表示。"O(N log N)"表示"对某常数 c，操作次数至多为 c × N × log(N)"。用于比较算法效率。

二分查找（Binary Search） 有序数组上的 O(log N) 搜索算法。每步与中点比较，将候选范围减半。最重要的应用："对答案二分"用于优化问题。

暴力枚举（Brute Force） 尝试所有可能情况的朴素解法。通常为 O(N²) 或 O(2^N)。正确但对大规模输入太慢。用途：部分得分、验证优化解、小测试用例。

C

比较器（Comparator） 定义排序顺序的函数。接收两个元素，若第一个应排在第二个前面则返回 true。与 std::sort 配合使用。

算法竞赛（Competitive Programming） 在时间限制内解决算法问题的编程竞赛。USACO、Codeforces、LeetCode 和 IOI 是热门平台。

连通分量（Connected Component） 任意两顶点之间都有路径相连的极大子图。可用 DFS/BFS 或并查集找连通分量。

坐标压缩（Coordinate Compression） 将大范围的值（如最大 10^9）映射为小的连续下标（0, 1, 2, ...）而不改变相对顺序。使得可以用数组代替哈希表。

D

DAG（有向无环图，Directed Acyclic Graph） 没有环的有向图。关键性质：存在拓扑排序。示例：依赖关系图、任务调度。

DFS（深度优先搜索，Depth-First Search） 在回溯前尽可能深地探索的图遍历。使用栈（或递归）。适用于：连通性判断、环检测、拓扑排序。时间复杂度：O(V + E)。

差分数组（Difference Array） O(1) 区间更新的技术。存储相邻元素之差；区间加 [L,R] 变为 diff[L]++ 和 diff[R+1]--。用前缀和还原原数组。

DP（动态规划，Dynamic Programming） 通过将问题分解为有重叠的子问题并缓存结果来优化求解的技术。需要两个性质：最优子结构 + 重叠子问题。另见：记忆化、递推。

DSU（并查集，Disjoint Set Union） 见"并查集（Union-Find）"。

E

边（Edge） 图中两顶点之间的连接。可以是有向的（单向）或无向的（双向），可以有权重。

交换论证（Exchange Argument） 贪心算法的证明技术。证明将贪心选择与其他选择交换后，解不会变得更差。

F

洪水填充（Flood Fill） 一种算法（通常用 DFS 或 BFS），标记网格中所有相同"颜色"的连通格子。用于统计连通区域数。

G

图（Graph） 由顶点（节点）和边（连接）组成的数据结构。建模关系、网络、地图等。

贪心算法（Greedy Algorithm） 在每步做出局部最优选择，期望得到全局最优结果的算法。当"贪心选择性质"成立时有效。示例：活动选择、哈夫曼编码、Kruskal MST。

H

哈希表（Hash Map / unordered_map） 以 O(1) 平均时间存储和查找键值对的数据结构。用哈希表实现。没有顺序保证。当需要快速查找但不需要有序键时使用。

I

区间 DP（Interval DP） 以子数组 [l, r] 为状态，尝试所有分割点的 DP 模式。经典示例：矩阵链乘法、回文划分。时间复杂度：O(N³)。

K

背包问题（Knapsack Problem） DP 问题：给定有重量和价值的物品，在重量限制内最大化价值。"0/1 背包"指每件物品最多使用一次，"完全背包"指可以无限使用。

L

LIS（最长递增子序列，Longest Increasing Subsequence） 数组中每个元素都严格大于前一个元素的最长子序列。O(N²) DP 或带二分查找的 O(N log N)。

LCA（最近公共祖先，Lowest Common Ancestor） 有根树中同时是 u 和 v 的祖先的最深节点。朴素做法：每次查询 O(深度)。倍增：O(log N)。

M

记忆化（Memoization） 缓存递归函数调用结果以避免重复计算。"自顶向下 DP"。备忘录表存储已计算的值；计算前先检查答案是否已知。

MST（最小生成树，Minimum Spanning Tree） 带权图中总边权最小的生成树。Kruskal 算法：排序边 + 并查集。Prim 算法：优先队列 + 已访问集合。两者都是 O(E log E)。

单调（Monotone / Monotonic） 持续递增或递减。函数单调意味着方向从不反转。对答案二分的关键：可行性函数必须是单调的。

O

差一错误（Off-By-One Error） 下标或计数恰好差 1 的 Bug。在循环（< n vs <= n）、二分查找、前缀和（P[L-1] vs P[L]）中非常常见。

最优子结构（Optimal Substructure） 一种性质：问题的最优解可以由其子问题的最优解构建。DP 正常工作的必要条件。

溢出（Overflow） 值超过类型所能表示的最大值。int 最大值约为 2×10^9；long long 最大值约为 9.2×10^18。两个 10^9 的 int 相乘会溢出 int——先强制转换为 long long。

P

前缀和（Prefix Sum） P[i] = 从下标 0（或 1）到 i 所有元素之和的数组。支持 O(1) 区间查询：sum(L,R) = P[R] - P[L-1]。

R

递推关系（Recurrence Relation） 将 DP 值表示为更小 DP 值的公式。示例：fib(n) = fib(n-1) + fib(n-2)。定义了 DP 的状态转移。

S

线段树（Segment Tree） 支持 O(log N) 区间查询和更新的数据结构。比前缀和更强大（支持更新）。Gold/Platinum 级别话题。

稀疏图（Sparse Graph） 边数相对于 V² 较少的图。实践中：E = O(V)。使用邻接表。

状态（DP State） 唯一标识 DP 子问题的信息集合。背包中的示例：(物品下标, 剩余容量)。选择合适的状态是 DP 的核心技能。

子树（Subtree） 树中某节点的所有后代节点（含该节点本身）。树形 DP 通常计算子树上的聚合值。

T

递推（Tabulation） 从边界条件到更大子问题迭代构建 DP 表格。"自底向上 DP"。无递归，无栈溢出风险。

超时（Time Limit Exceeded / TLE） 评测结果之一，表示解法正确但速度太慢。USACO 中大多数题目的时间限制为 2~4 秒。遇到 TLE，优化算法——而不只是优化常数因子。

拓扑排序（Topological Sort） DAG 中顶点的一种排序方式，使得对每条有向边 u→v，u 都排在 v 前面。可用 DFS（逆后序）或 Kahn 算法（基于 BFS）计算。

双指针（Two Pointers） 使用两个下标遍历数组（通常同向移动）的技术。将 O(N²) 的配对搜索转化为 O(N)。适用于有序数组或条件单调的情形。

U

并查集（Union-Find / DSU） 支持两种操作的数据结构：find(x)（x 属于哪个集合？）和 union(x,y)（合并 x 和 y 所在的集合）。带路径压缩 + 按秩合并：每次操作 O(α(N)) ≈ O(1)。用于动态连通性、Kruskal MST、环检测。

V

顶点（Vertex / Node） 图的基本单元。顶点有编号（USACO 中通常从 1 开始）。

W

答案错误（Wrong Answer / WA） 评测结果之一，表示程序运行了但输出了错误结果。检查边界情况、差一错误和整数溢出。