第 9 讲 · 程序设计竞赛入门路线

源目录中的《深入浅出程序设计竞赛》不是一讲幻灯片，而是一本 327 页的补充教材。它从语言入门一路讲到基础算法、数据结构和数学。这里不抄整本书，而是把 21 章压成一张可执行的学习地图：知道每类问题在问什么、适用条件是什么、最小代码骨架怎么写。

1. 原书四部分对应什么能力

部分	原书章节	要形成的能力
语言入门	1～7：简单程序、顺序、分支、循环、数组、字符串与文件、函数与结构体	把题意写成可靠程序
初步算法	8～14：模拟、高精度、排序、暴力枚举、递推递归、贪心、二分、搜索	从规模和结构选择算法
简单数据结构	15～18：线性表、树、集合、图	选择合适的数据组织方式
基础数学与数论	19～21：位运算与进制、计数、整数理论	把数学规律变成更快算法

前七章的大部分语言基础已经分散在本系列第 2～8 讲。补充教材还明确加入了文件、结构体和竞赛复杂度，这里先补齐，再进入算法部分。

2. 文件与结构体：语言部分的两个补充点

2.1 文件操作

FILE *input = fopen("data.txt", "r");
if (input == NULL) {
    return 1;
}

int x;
while (fscanf(input, "%d", &x) == 1) {
    /* 处理 x */
}

fclose(input);

文件模式 r、w、a 分别表示读取、覆盖写入和追加。真实程序要检查打开和读写是否成功，并保证每个成功打开的文件最终关闭。OJ 通常仍从标准输入输出读写，不应硬编码本地文件名。

2.2 结构体

typedef struct {
    int id;
    char name[32];
    int score;
} Student;

Student lee = {23371100, "Lee", 95};
printf("%s %d\n", lee.name, lee.score);

结构体把不同类型但属于同一实体的数据绑在一起。结构体变量可以整体赋值；传给函数时默认仍是值复制，大对象常传 const Student * 避免复制并表达只读。

3. 先看数据规模，再选算法

复杂度描述输入变大时操作数怎样增长：

复杂度	$n=10^5$ 时的直觉
$O(1)$	与 $n$ 无关
$O(\log n)$	约十几次到几十次
$O(n)$	通常轻松
$O(n\log n)$	常见排序规模
$O(n^2)$	约 $10^{10}$ ，通常不可行
$O(2^n)$ 、 $O(n!)$	只能处理很小的 $n$

空间复杂度同样重要。能用公式计数时，不要真的开一个巨型二维数组逐格模拟。

4. 模拟：忠实维护状态

模拟题不是“没算法”，而是把规则翻译成状态机。补充教材用乒乓球、扫雷和玩具谜题说明三类关键点：

识别当前状态需要哪些变量；
每条规则触发时怎样更新状态；
坐标移动、边界和全面考虑是否完整。

写模拟前列一张表：

状态：当前位置、方向、分数、回合……
事件：读到一个操作或输入
转移：旧状态 + 事件 → 新状态
输出：什么时候产生，格式是什么

若规则很多，把每个动作拆成函数。不要让一段几百行的 main 同时负责输入、状态转移和输出。

5. 高精度：用数组表示超大整数

内置整数放不下时，可把每个十进制位存在数组里，低位放前面便于进位：

12345  存为  [5, 4, 3, 2, 1]

高精度加法逐位做：

#include <algorithm>
#include <vector>

std::vector<int> add(const std::vector<int>& a,
                     const std::vector<int>& b)
{
    std::vector<int> c;
    int carry = 0;
    std::size_t n = std::max(a.size(), b.size());
    for (std::size_t i = 0; i < n || carry; ++i) {
        int sum = carry;
        if (i < a.size()) sum += a[i];
        if (i < b.size()) sum += b[i];
        c.push_back(sum % 10);
        carry = sum / 10;
    }
    return c;
}

乘法与小学竖式相同：第 $i$ 、 $j$ 位乘积累加到第 $i+j$ 位，再统一进位。补充教材还以幂和为例说明把高精度加、乘封装成结构或类，并在 C++ 中用运算符重载改善表达；本质仍是数组、进位和符号管理。

6. 排序：让无序数据获得结构

补充教材从计数排序、选择/冒泡/插入、快速排序讲到排序应用。

6.1 计数排序

值域很小时，统计每个值出现次数：

int count[MAX_VALUE + 1] = {0};
for (int i = 0; i < n; ++i) {
    ++count[a[i]];
}
for (int value = 0; value <= MAX_VALUE; ++value) {
    while (count[value] > 0) {
        printf("%d ", value);
        --count[value];
    }
}

时间约为 $O(n+V)$ ，其中 $V$ 是值域；若值域巨大就会浪费空间。

6.2 快速排序的划分思想

选一个枢轴，把较小元素放一侧、较大元素放另一侧，再递归处理两边。平均 $O(n\log n)$ ，最坏 $O(n^2)$ 。实战中优先使用库排序，并专心写正确比较规则。

6.3 排序后的应用

原书还覆盖：

去重：排序后相同值相邻；
结构体排序：把多个关键字写进比较函数；
字符串排序：用字典序或自定义规则；
借用排序思想求第 $k$ 小等次序统计问题。

7. 暴力枚举：先保证不漏，再想剪枝

暴力的核心是覆盖全部候选，而不是无脑多层循环。

7.1 循环枚举

变量个数固定、范围小，可直接嵌套循环。每增加一层，候选数相乘，必须估算规模。

7.2 子集枚举

$n$ 个元素的每个子集可用 $n$ 位二进制表示：

for (unsigned mask = 0; mask < (1u << n); ++mask) {
    for (int i = 0; i < n; ++i) {
        if ((mask >> i) & 1u) {
            /* 第 i 个元素被选中 */
        }
    }
}

复杂度至少为 $O(n2^n)$ ，只适合较小 $n$ 。集合的并、交、包含、补集也可在位掩码上用 |、&、子集判断和取反表达。

7.3 排列枚举

C++ 可从有序序列开始反复调用 next_permutation：

#include <algorithm>

std::sort(a.begin(), a.end());
do {
    /* 使用当前排列 */
} while (std::next_permutation(a.begin(), a.end()));

共有 $n!$ 个排列，增长极快。若只需计数或可提前判错，应避免生成所有排列。

8. 递推与递归

递推从已知初值向前计算，例如数楼梯、二维递推；通常用数组或少量滚动变量保存状态。

递归则从目标反向拆成更小目标，适合树状结构、分治与自然定义。原书以数的计算、Function 和外星密码等问题说明复杂递归，重点仍是：

明确函数参数代表的子问题；
写基本情况；
保证规模缩小；
避免重复子问题，必要时记忆化。

long long memo[MAX_N];

long long solve(int n)
{
    if (n <= 1) return 1;
    if (memo[n] != 0) return memo[n];
    return memo[n] = solve(n - 1) + solve(n - 2);
}

记忆化把递归树里重复节点合并，是动态规划的入口。

9. 贪心：每一步局部最优必须能证明

贪心每次做当前看起来最好的选择，之后不回退。它并非对所有问题都正确。

9.1 怎样判断一个贪心是否可信

贪心选择性质：存在一个最优解包含当前选择；
最优子结构：做完选择后，剩余部分仍是同类最优问题；
交换论证：任意最优解都能替换成包含当前选择的解而不变差；
或者找反例推翻错误策略。

例如 0/1 背包按单位价值拿取会失败，因为物品不可拆；分数背包则可以这样贪心。原书以部分背包、排队接水等例子展示证明与反例。

9.2 Huffman 合并

反复取最小的两个权值合并，将和放回集合：

每一步拿两个最小值 → 合并成本加入答案 → 新权值放回

用最小堆实现为 $O(n\log n)$ 。分果子、合并果子以及 Huffman 编码都复用这一结构。

10. 二分查找与二分答案

10.1 有序数组查找

每次比较中点，排除不可能的一半区间，复杂度 $O(\log n)$ 。

10.2 二分答案

不直接知道答案，但能写出单调判定 ok(x)：

x 太小：不可行
x 足够大：可行

就可以找最小可行值：

long long left = low;
long long right = high;

while (left < right) {
    long long mid = left + (right - left) / 2;
    if (ok(mid)) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

二分前必须证明单调性，确定边界一定包住答案，并明确寻找“第一个可行”还是“最后一个可行”。

11. 深度优先搜索与回溯

DFS 沿一条路走到底，再退回来尝试下一条。回溯模板：

void dfs(int step)
{
    if (step == target) {
        record_answer();
        return;
    }

    for (int choice = 0; choice < choice_count; ++choice) {
        if (!valid(choice)) continue;
        make_choice(choice);
        dfs(step + 1);
        undo_choice(choice);
    }
}

“做选择—递归—撤销选择”缺一不可。四阶数独、八皇后等问题还可通过提前检测冲突剪掉不可能分支。

12. 广度优先搜索

BFS 从起点按距离一层层扩展，需要队列：

queue[tail++] = start;
visited[start] = 1;

while (head < tail) {
    int u = queue[head++];
    for (每个从 u 可达的 v) {
        if (!visited[v]) {
            visited[v] = 1;
            distance[v] = distance[u] + 1;
            queue[tail++] = v;
        }
    }
}

在每条边代价相同的无权图中，第一次到达节点就是最短步数。visited 应在入队时设置，避免同一节点被重复加入。

13. 线性表：数组、栈、队列和链表

13.1 数组与 C++ `vector`

数组支持 $O(1)$ 下标访问；中间插入删除需要搬移元素。C++ vector 是动态连续数组，支持迭代器和自动扩容，但扩容可能使旧指针、引用和迭代器失效。

13.2 栈

后进先出，典型应用：括号匹配、后缀表达式、函数调用。操作为 push、pop、top。

13.3 队列

先进先出，用于 BFS、排队模拟。数组实现应采用循环队列或单调移动的头尾下标，避免每次出队都搬动全部元素。

13.4 链表

每个节点保存数据和下一个节点地址：

typedef struct Node {
    int value;
    struct Node *next;
} Node;

已知节点位置时插入删除只改指针，但按下标查找是 $O(n)$ ，每个节点还需要额外地址空间。操作时要处理空表、头节点、尾节点和释放责任。

14. 树、集合与图

14.1 二叉树

二叉树每个节点最多两个孩子。递归遍历：

前序：根—左—右；
中序：左—根—右；
后序：左—右—根。

层序遍历则使用队列。创建树时要明确空节点的输入标记；遍历复杂度通常为 $O(n)$ 。

14.2 并查集

并查集维护“哪些元素属于同一集合”，支持查找代表元和合并：

int find(int x)
{
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a != b) parent[a] = b;
}

路径压缩配合按秩或按大小合并，均摊效率几乎为常数。它适合动态连通性，不适合直接回答两点最短路。

14.3 哈希表与集合

哈希函数把关键字映射到桶，冲突可用链地址或开放寻址解决。平均查找接近 $O(1)$ ，但依赖哈希质量、装载因子和冲突处理；它不自动维护排序。

C++ 的 set 通常有序、操作 $O(\log n)$ ；unordered_set 基于哈希，平均 $O(1)$ ，顺序不确定。

14.4 图与拓扑排序

图由顶点和边组成，可用邻接矩阵或邻接表表示：

邻接矩阵简单，空间 $O(V^2)$ ；
邻接表适合稀疏图，空间 $O(V+E)$ 。

DFS、BFS 都能遍历图，但必须记录访问状态避免环。

有向无环图（DAG）的拓扑排序按入度推进：把所有入度为 0 的点入队，依次删除其出边；若最终处理顶点数少于 $V$ ，图中存在环。

15. 位运算、进制与逻辑命题

原书第四部分先回到二进制，覆盖各种进制、二进制深入探究和逻辑命题。实战常见技巧：

int bit = (x >> k) & 1u;  /* 取第 k 位 */
x |= 1u << k;             /* 置位 */
x &= ~(1u << k);          /* 清位 */
x ^= 1u << k;             /* 翻转 */

条件命题也可用真值表检查。德摩根律尤其适合把否定推进条件内部：

\neg(A\land B)=\neg A\lor\neg B, \qquad \neg(A\lor B)=\neg A\land\neg B.

16. 计数原理、排列与组合

加法原理：互斥方案数相加；
乘法原理：连续独立步骤的选择数相乘；
排列：考虑顺序；
组合：不考虑顺序。

P(n,k)=\frac{n!}{(n-k)!}, \qquad C(n,k)=\frac{n!}{k!(n-k)!}.

计算组合数不应盲目先算三个阶乘，可用递推：

C(n,k)=C(n-1,k-1)+C(n-1,k)

或在能整除的顺序中边乘边除。结果是否需要取模、模数是否为质数，会决定能否使用模逆元等更进阶方法。

17. 整数理论

17.1 质数与合数

判断单个 $n$ 是否为质数，只需试除到 $\sqrt n$ ：

int is_prime(int n)
{
    if (n < 2) return 0;
    for (int d = 2; d <= n / d; ++d) {
        if (n % d == 0) return 0;
    }
    return 1;
}

d <= n / d 避免 d * d 溢出。若要得到一个范围内所有质数，使用筛法更合适。

17.2 最大公约数与最小公倍数

long long gcd(long long a, long long b)
{
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

\operatorname{lcm}(a,b)=\frac{|a|}{\gcd(a,b)}|b|.

先除后乘能降低溢出概率。

17.3 模运算与快速幂

模运算满足加法、乘法可先取模：

(a+b)\bmod m=((a\bmod m)+(b\bmod m))\bmod m,

(ab)\bmod m=((a\bmod m)(b\bmod m))\bmod m.

二进制快速幂在 $O(\log b)$ 次乘法内求 $a^b\bmod m$ ：

long long power_mod(long long a, long long b, long long mod)
{
    long long result = 1 % mod;
    a %= mod;
    while (b > 0) {
        if (b & 1) result = result * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return result;
}

若乘积可能超过 long long，还需更宽类型或安全乘法；“每步取模”不能自动消除乘法本身的溢出。

18. 把整本补充材料变成解题顺序

拿到题目后依次问：

能否按规则直接模拟？状态和边界是什么？
数值是否超出内置类型，需要高精度吗？
排序后是否更容易去重、查找或贪心？
数据很小，能否枚举子集或排列？
是否存在递推关系、独立子问题或重复子问题？
局部最优能证明得到全局最优吗？
答案或判定是否单调，可以二分吗？
状态空间需要 DFS 还是 BFS？
数据关系更像栈、队列、树、集合还是图？
是否有进制、计数、质数、最大公约数或模运算规律？

这 10 个问题，就是从“会写 C”走向“会用程序解题”的第一张路线图。