# C++11 算法基础讲义

本讲义旨在系统梳理程序设计中常见的算法思想与技术。为契合高性能与低开销的要求，并遵循“尽量避免自定义结构体和指针”的原则，所有代码均采用 **C++11 标准**，核心数据结构多使用**静态一维/多维数组、标准库辅助容器（如 `std::vector`、`std::pair`）与独立函数**进行设计。

---

## 1. 算法概念与描述

### 1.1 算法基本概念
算法（Algorithm）是解决特定问题的一系列明确、有限的步骤。一个合法的算法应具备以下五个重要特性：
1.  **有穷性**：算法在执行有限步后必须结束，且每一步都在有穷时间内完成。
2.  **确定性**：算法中的每一条指令都有确切的含义，无二义性。
3.  **可行性**：算法中的所有操作都可以通过已经实现的基本运算执行有限次来实现。
4.  **输入**：有零个或多个输入。
5.  **输出**：有一个或多个输出。

衡量算法优劣的核心指标为**时间复杂度**（主要关注最坏情况下的渐进时间复杂度）与**空间复杂度**，通常使用大 $O$ 符号表示。

### 1.2 算法描述方法
*   **自然语言**：用人类日常语言描述步骤，易理解但容易产生歧义。
*   **流程图**：用统一规定的图形符号（如起止框、处理框、判断框等）直观表达逻辑，适合较简单的控制流。
*   **伪代码**：介于自然语言与程序设计语言之间，用类似代码的结构化语言来表述算法逻辑，忽略具体语法细节，便于算法的设计与交流。

---

## 2. 入门算法

### 2.1 枚举法 (Enumeration)
枚举法（又称暴力搜索法）是根据问题本身的规律，逐一列举所有可能的解，并根据约束条件判断其是否为合法的解。

*   **优化策略**：
    *   缩小枚举范围。
    *   避免重复计算。

#### 示例：求 $[2, N]$ 之间的所有素数（枚举因子法）
```cpp
#include <iostream>

// 时间复杂度 O(N * sqrt(N))
bool is_prime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i) { // 仅枚举到 sqrt(n)
        if (n % i == 0) return false;
    }
    return true;
}

void enumerate_primes(int n) {
    for (int i = 2; i <= n; ++i) {
        if (is_prime(i)) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
}
```

### 2.2 模拟法 (Simulation)
模拟法是指根据题目描述的规则、过程和步骤，用代码一步步重现该过程，从而得到结果。模拟算法通常不涉及高深的数学推导，但要求代码对细节控制十分精准。

#### 示例：顺时针旋转 $N \times N$ 矩阵 $90^\circ$
设原矩阵为 $A$，旋转后矩阵为 $B$。通过观察几何关系可知，原矩阵的第 $i$ 行第 $j$ 列，旋转后会变成第 $j$ 行第 $N - 1 - i$ 列：
$$B[j][N - 1 - i] = A[i][j]$$

```cpp
#include <iostream>

const int MAX_N = 105;
int mat[MAX_N][MAX_N];
int rotated[MAX_N][MAX_N];

void rotate_matrix(int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            rotated[j][n - 1 - i] = mat[i][j];
        }
    }
}
```

---

## 3. 基础算法

### 3.1 贪心算法 (Greedy)
贪心算法在求解问题时，总是做出在当前看来是最好的选择。也就是说，它不从整体最优上加以考虑，所做出的仅是局部最优解。
*   **适用条件**：
    1.  **贪心选择性质**：整体最优解可以通过一系列局部最优（贪心）选择达到。
    2.  **最优子结构**：一个问题的最优解包含其子问题的最优解。
*   **证明方法**：常见证明有**反证法**和**归纳法（如微调/交换论证 Exchange Argument）**。

#### 示例：区间选点问题（选择最少的点，使每个给定闭区间都至少包含一个点）
**贪心策略**：将所有区间按**右端点从小到大**排序。每次选择当前未覆盖区间的右端点，以此点覆盖尽可能多的区间。

```cpp
#include <iostream>
#include <algorithm>
#include <vector>

// 使用 std::pair<int, int> 存储区间，first 为右端点，second 为左端点
// 这样默认排序时会先根据右端点（first）排序
int select_points(std::vector<std::pair<int, int>>& intervals) {
    if (intervals.empty()) return 0;
    
    std::sort(intervals.begin(), intervals.end());
    
    int count = 1;
    int last_point = intervals[0].first; // 选择第一个区间的右端点
    
    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i].second > last_point) { // 如果当前区间的左端点大于上一个选点，说明无法覆盖
            count++;
            last_point = intervals[i].first;    // 在当前区间的右端点放新点
        }
    }
    return count;
}
```

### 3.2 递推法 (Recurrence)
递推法是指根据已知的初始状态，通过一个明确的数学递推公式，一步步推导出未知状态。

#### 示例：错排问题 (Derangement)
有 $n$ 个信封和 $n$ 封信，每封信都装错的方案数记为 $D(n)$。
*   **公式递推推导**：
    1. 设第 $n$ 封信放入了第 $i$ 个信封（有 $n-1$ 种选择，假设 $i=1$）。
    2. 此时考虑第 1 封信的去向：
       * 若第 1 封信放入了第 $n$ 个信封，则剩下的 $n-2$ 封信和信封形成错排，方案数为 $D(n-2)$。
       * 若第 1 封信没有放入第 $n$ 个信封，则第 1 到第 $n-1$ 封信必须错排放在除第 1 个以外的 $n-1$ 个信封中（将第 $n$ 个信封视作原第 1 封信的“禁区”），方案数为 $D(n-1)$。
    3. 综合可得递推公式：
       $$D(n) = (n - 1) \cdot (D(n - 1) + D(n - 2))$$

```cpp
long long d[105];

void init_derangement(int n) {
    d[1] = 0;
    d[2] = 1;
    for (int i = 3; i <= n; ++i) {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
    }
}
```

### 3.3 递归法 (Recursion)
递归指一个函数直接或间接地调用自身。
*   **核心要素**：
    1.  **递归出口（边界条件）**：防止无限递归导致栈溢出（Stack Overflow）。
    2.  **递归递推关系**：如何将大问题分解为小问题。

#### 示例：汉诺塔 (Tower of Hanoi) 移动步骤输出
```cpp
#include <iostream>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        std::cout << "Move disk 1 from " << from << " to " << to << std::endl;
        return;
    }
    hanoi(n - 1, from, aux, to);
    std::cout << "Move disk " << n << " from " << from << " to " << to << std::endl;
    hanoi(n - 1, aux, to, from);
}
```

### 3.4 二分法 (Binary Search)
二分法是将区间逐步折半以寻找特定目标或边界的算法。其时间复杂度为 $O(\log N)$。

#### 1. 整数二分模板 (寻找单调序列边界)
处理整数二分时，最棘手的是边界问题。以下提供两套常用模板：

##### 模板 1：寻找符合条件 $Q$ 的**左边界**（最左侧符合条件的值，如 `std::lower_bound`）
```cpp
int binary_search_left(int q[], int n, int target) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l) / 2; // 向下取整，避免溢出
        if (q[mid] >= target) {
            r = mid; // 答案在左半边（包含 mid）
        } else {
            l = mid + 1; // 答案在右半边（不含 mid）
        }
    }
    return q[l] == target ? l : -1;
}
```

##### 模板 2：寻找符合条件 $Q$ 的**右边界**
```cpp
int binary_search_right(int q[], int n, int target) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2; // 向上取整，配合 l = mid 防止死循环
        if (q[mid] <= target) {
            l = mid; // 答案在右半边（包含 mid）
        } else {
            r = mid - 1; // 答案在左半边（不含 mid）
        }
    }
    return q[l] == target ? l : -1;
}
```

#### 2. 实数二分
实数二分无边界整除带来的死循环风险，只需根据精度（$\epsilon$）或循环固定次数进行迭代。
```cpp
double real_binary_search(double l, double r, double target) {
    const double eps = 1e-7;
    while (r - l > eps) {
        double mid = l + (r - l) / 2.0;
        if (mid * mid >= target) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return l;
}
```

### 3.5 倍增法 (Doubling)
倍增法核心思想是“按 2 的幂次递增”，将线性扫描转换为跳跃式扫描，常用于构造 ST 表（解决 RMQ 问题）以及求树的最近公共祖先（LCA）。

#### 示例：ST 表 (Sparse Table) 求解区间最大值
*   **性质**：$f[i][j]$ 表示以 $i$ 为起点，长度为 $2^j$ 的区间内的最大值。
*   **状态转移方程**：
    $$f[i][j] = \max(f[i][j - 1], f[i + 2^{j - 1}][j - 1])$$

```cpp
#include <algorithm>
#include <cmath>

const int MAX_LEN = 100010;
const int LOG_MAX = 20;
int f[MAX_LEN][LOG_MAX];
int lg[MAX_LEN]; // 预处理 log 数组

void init_st(int arr[], int n) {
    // 1. 预处理 log 数组
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }
    
    // 2. 初始化第一列
    for (int i = 1; i <= n; ++i) {
        f[i][0] = arr[i];
    }
    
    // 3. 动态规划递推
    for (int j = 1; j < LOG_MAX; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// 查询 [L, R] 的最大值
int query_st(int l, int r) {
    int k = lg[r - l + 1];
    return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}
```

---

## 4. 算法策略

### 4.1 前缀和 (Prefix Sum)
前缀和能将区间求和的复杂度由 $O(N)$ 降到 $O(1)$。

#### 1. 一维前缀和
设原数组为 $A$，前缀和数组为 $S$，$S[i] = \sum\_{j=1}^{i} A[j]$。
*   **区间求和**：$[L, R]$ 之间的元素和为 $S[R] - S[L - 1]$。

#### 2. 二维前缀和
设 $S[i][j]$ 表示以 $(1,1)$ 为左上角，$(i,j)$ 为右下角的子矩阵元素和。
*   **递推构造公式**（容斥原理）：
    $$S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j]$$
*   **子矩阵和查询**（求左上角 $(x\_1, y\_1)$ 到右下角 $(x\_2, y\_2)$ 的元素和）：
    $$\text{Sum} = S[x\_2][y\_2] - S[x\_1 - 1][y\_2] - S[x\_2][y\_1 - 1] + S[x\_1 - 1][y\_1 - 1]$$

```cpp
int s2d[MAX_N][MAX_N];

void build_2d_prefix(int a[MAX_N][MAX_N], int row, int col) {
    for (int i = 1; i <= row; ++i) {
        for (int j = 1; j <= col; ++j) {
            s2d[i][j] = s2d[i-1][j] + s2d[i][j-1] - s2d[i-1][j-1] + a[i][j];
        }
    }
}
```

### 4.2 差分 (Difference)
差分是前缀和的逆运算，能将区间加减的操作复杂度由 $O(N)$ 降到 $O(1)$。

#### 1. 一维差分
若 $B[i] = A[i] - A[i - 1]$（其中 $A[0] = 0$），则 $B$ 是 $A$ 的差分数组，$A$ 是 $B$ 的前缀和数组。
*   **区间加减**：若要在原数组区间 $[L, R]$ 上全部加上值 $C$，只需对差分数组操作：
    $$B[L] \leftarrow B[L] + C, \quad B[R + 1] \leftarrow B[R + 1] - C$$

#### 2. 二维差分
对以 $(x\_1, y\_1)$ 为左上角，$(x\_2, y\_2)$ 为右下角的子矩阵全部加上值 $C$，操作差分数组 $D$ 的方法为：
$$D[x\_1][y\_1] += C, \quad D[x\_2+1][y\_1] -= C, \quad D[x\_1][y\_2+1] -= C, \quad D[x\_2+1][y\_2+1] += C$$

```cpp
int d2d[MAX_N][MAX_N];

void add_2d_diff(int x1, int y1, int x2, int y2, int c) {
    d2d[x1][y1] += c;
    d2d[x2 + 1][y1] -= c;
    d2d[x1][y2 + 1] -= c;
    d2d[x2 + 1][y2 + 1] += c;
}

// 恢复原矩阵：对差分矩阵求一次二维前缀和即可
```

---

## 5. 数值处理（高精度运算）

当数值超出 `long long` 的表示范围（例如达到 $10^{100}$ 甚至更高）时，需要用数组来模拟手算过程。在代码中，我们使用 `std::vector<int>` 逆序存储大数（即个位存储在 `vector[0]`，便于最高位进位时在尾部直接 `push_back`）。

### 5.1 高精度加法
```cpp
#include <vector>
#include <string>

std::vector<int> add_high_precision(const std::vector<int>& A, const std::vector<int>& B) {
    std::vector<int> C;
    int t = 0; // 进位
    for (size_t i = 0; i < A.size() || i < B.size(); ++i) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}
```

### 5.2 高精度减法
```cpp
// 辅助判定 A >= B
bool compare_high_precision(const std::vector<int>& A, const std::vector<int>& B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; --i) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

std::vector<int> sub_high_precision(const std::vector<int>& A, const std::vector<int>& B) {
    std::vector<int> C;
    int t = 0; // 借位
    for (size_t i = 0; i < A.size(); ++i) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    // 去除前导 0，但保证至少剩下一个数
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
```

### 5.3 高精度乘法（高精度 $\times$ 低精度）
```cpp
std::vector<int> mul_high_precision(const std::vector<int>& A, int b) {
    std::vector<int> C;
    int t = 0; // 乘积与进位
    for (size_t i = 0; i < A.size() || t; ++i) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前导0
    return C;
}
```

### 5.4 高精度除法（高精度 $\div$ 低精度）
```cpp
#include <algorithm>

// 返回商，r 作为引用传回余数
std::vector<int> div_high_precision(const std::vector<int>& A, int b, int& r) {
    std::vector<int> C;
    r = 0; // 余数
    // 除法从最高位开始算
    for (int i = A.size() - 1; i >= 0; --i) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    std::reverse(C.begin(), C.end()); // 翻转以保持低位在前
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
```

---

## 6. 排序算法

此处实现经典的四种初等排序，并统一分析其复杂度与稳定性。

| 算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
| :--- | :--- | :--- | :--- | :--- |
| **冒泡排序** | $O(N)$（带优化） | $O(N^2)$ | $O(1)$ | 稳定 |
| **选择排序** | $O(N^2)$ | $O(N^2)$ | $O(1)$ | 不稳定 |
| **插入排序** | $O(N)$ | $O(N^2)$ | $O(1)$ | 稳定 |
| **计数排序** | $O(N + K)$ | $O(N + K)$ | $O(N + K)$ | 稳定 |

### 6.1 冒泡排序 (Bubble Sort)
```cpp
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool has_swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                has_swapped = true;
            }
        }
        if (!has_swapped) break; // 若某趟未发生交换，说明已有序
    }
}
```

### 6.2 选择排序 (Selection Sort)
```cpp
void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        std::swap(arr[i], arr[min_idx]);
    }
}
```

### 6.3 插入排序 (Insertion Sort)
```cpp
void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int val = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > val) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = val;
    }
}
```

### 6.4 计数排序 (Counting Sort)
```cpp
#include <cstring>

const int K_RANGE = 100010; // 假设数据范围非负且不大于该值
int count_arr[K_RANGE];
int temp_arr[MAX_LEN];

void counting_sort(int arr[], int n) {
    std::memset(count_arr, 0, sizeof(count_arr));
    
    // 1. 统计频率
    for (int i = 0; i < n; ++i) {
        count_arr[arr[i]]++;
    }
    
    // 2. 累加频率，使其表示位置
    for (int i = 1; i < K_RANGE; ++i) {
        count_arr[i] += count_arr[i - 1];
    }
    
    // 3. 逆序构建以保持稳定性
    for (int i = n - 1; i >= 0; --i) {
        temp_arr[count_arr[arr[i]] - 1] = arr[i];
        count_arr[arr[i]]--;
    }
    
    // 4. 写回原数组
    for (int i = 0; i < n; ++i) {
        arr[i] = temp_arr[i];
    }
}
```

---

## 7. 搜索算法 与 8. 图论基础算法

### 7.1 DFS（深度优先搜索）与 BFS（广度优先搜索）在迷宫中的应用

我们使用平行静态数组记录迷宫状态与路径信息，完全避开自定义点结构体。

```cpp
#include <queue>
#include <utility>

const int g_rows = 5, g_cols = 5;
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 1, 0},
    {1, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};
bool visited[5][5];

// 移动方向：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 1. DFS 寻找任意可行通路
bool dfs_maze(int x, int y) {
    if (x == g_rows - 1 && y == g_cols - 1) return true; // 到达终点
    visited[x][y] = true;
    
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < g_rows && ny >= 0 && ny < g_cols) {
            if (!visited[nx][ny] && maze[nx][ny] == 0) {
                if (dfs_maze(nx, ny)) return true;
            }
        }
    }
    return false;
}

// 2. BFS 寻找最短路径步数
int bfs_maze_steps() {
    std::queue<std::pair<int, int>> q; // 存储坐标 {x, y}
    int dist[5][5];                    // 记录距离
    std::fill(&dist[0][0], &dist[0][0] + 25, -1);
    
    q.push(std::make_pair(0, 0));
    dist[0][0] = 0;
    
    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        int cx = curr.first;
        int cy = curr.second;
        
        if (cx == g_rows - 1 && cy == g_cols - 1) return dist[cx][cy];
        
        for (int i = 0; i < 4; ++i) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx >= 0 && nx < g_rows && ny >= 0 && ny < g_cols) {
                if (dist[nx][ny] == -1 && maze[nx][ny] == 0) {
                    dist[nx][ny] = dist[cx][cy] + 1;
                    q.push(std::make_pair(nx, ny));
                }
            }
        }
    }
    return -1;
}
```

### 7.2 图的静态 DFS 与 BFS

使用上一讲的**链式前向星（静态邻接表）**实现。

```cpp
// 链式前向星全局变量
const int N_V = 10005;
const int M_E = 100005;
int head[N_V], to_node[M_E], next_edge[M_E], edge_cnt;
bool graph_vis[N_V];

// 图的 DFS
void dfs_graph(int u) {
    graph_vis[u] = true;
    for (int i = head[u]; i != -1; i = next_edge[i]) {
        int v = to_node[i];
        if (!graph_vis[v]) {
            dfs_graph(v);
        }
    }
}

// 图的 BFS
void bfs_graph(int start) {
    std::queue<int> q;
    q.push(start);
    graph_vis[start] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = next_edge[i]) {
            int v = to_node[i];
            if (!graph_vis[v]) {
                graph_vis[v] = true;
                q.push(v);
            }
        }
    }
}
```

### 7.3 泛洪算法 (Flood Fill)
泛洪算法常用于寻找网格图中的连通分量个数（如求孤岛、连通水域）。

```cpp
int grid[5][5]; // 假设非 0 表示有障碍，0 表示平地
bool fill_vis[5][5];

void flood_fill(int x, int y) {
    fill_vis[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
            if (!fill_vis[nx][ny] && grid[nx][ny] == 0) {
                flood_fill(nx, ny);
            }
        }
    }
}

int count_components() {
    int count = 0;
    std::fill(&fill_vis[0][0], &fill_vis[0][0] + 25, false);
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            if (!fill_vis[i][j] && grid[i][j] == 0) {
                count++;
                flood_fill(i, j); // 淹没所有与其连通的节点
            }
        }
    }
    return count;
}
```

---

## 9. 动态规划 (Dynamic Programming)

动态规划思想主要是通过将问题分解为相互重叠的子问题，并通过存储子问题的解来避免重复计算，常适用于具有**最优子结构**和**重叠子问题**性质的场景。

### 9.1 一维动态规划（最长上升子序列 LIS）
*   **状态设计**：$dp[i]$ 表示以 $arr[i]$ 结尾的最长上升子序列的长度。
*   **状态转移方程**：
    $$dp[i] = \max(1, dp[j] + 1) \quad (\text{其中 } 0 \le j < i \text{ 且 } arr[j] < arr[i])$$

```cpp
#include <algorithm>

int dp_lis[1005];

int get_lis_length(int arr[], int n) {
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        dp_lis[i] = 1; // 自身能形成一个长度为 1 的子序列
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) {
                dp_lis[i] = std::max(dp_lis[i], dp_lis[j] + 1);
            }
        }
        max_len = std::max(max_len, dp_lis[i]);
    }
    return max_len;
}
```

### 9.2 背包类型 DP

#### 1. 0/1 背包问题（滚动数组优化空间）
有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的重量是 $w[i]$，价值是 $v[i]$。每种物品仅有一件。
*   **状态设计**：$dp[j]$ 表示在容量为 $j$ 时的最大价值。
*   **转移方程推导**：
    原始转移方程：$dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])$。
    在降维优化时，为确保计算 $dp[j]$ 时，使用的是上一轮的 $dp[j-w[i]]$（防止同一件物品被多次放入），**内层循环必须逆序**。
    $$dp[j] = \max(dp[j], dp[j - w[i]] + v[i])$$

```cpp
int dp_01[10005]; // 大小为最大背包容量

int knapsack_01(int w[], int v[], int n, int bag_v) {
    std::fill(dp_01, dp_01 + bag_v + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = bag_v; j >= w[i]; --j) { // 逆序
            dp_01[j] = std::max(dp_01[j], dp_01[j - w[i]] + v[i]);
        }
    }
    return dp_01[bag_v];
}
```

#### 2. 完全背包问题
每种物品有无限多件。
*   **转移方程**：由于物品可以被多次选择，内层循环**必须正序**，从而可以在当前决策中累加该物品的多次贡献。
    $$dp[j] = \max(dp[j], dp[j - w[i]] + v[i])$$

```cpp
int dp_complete[10005];

int knapsack_complete(int w[], int v[], int n, int bag_v) {
    std::fill(dp_complete, dp_complete + bag_v + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = w[i]; j <= bag_v; ++j) { // 正序
            dp_complete[j] = std::max(dp_complete[j], dp_complete[j - w[i]] + v[i]);
        }
    }
    return dp_complete[bag_v];
}
```

### 9.3 区间类型 DP（经典：合并石子）
设有 $N$ 堆石子排成一排，每次只能合并相邻的两堆，合并的代价为两堆石子的重量之和。求将所有石子合并成一堆的最小代价。

*   **状态定义**：$dp[i][j]$ 表示合并第 $i$ 堆到第 $j$ 堆石子的最小代价。
*   **状态转移推导**：
    合并区间 $[i, j]$，可以看作是先把其分为两部分 $[i, k]$ 与 $[k + 1, j]$，然后再进行一次大合并。
    $$dp[i][j] = \min\_{i \le k < j}(dp[i][k] + dp[k + 1][j]) + \text{sum}(i, j)$$
    其中 $\text{sum}(i, j)$ 可通过前缀和 $O(1)$ 获得。
*   **计算顺序**：由于大区间的解依赖小区间的解，必须**按区间长度从短到长**开始循环递推。

```cpp
int dp_interval[305][305];
int stone_sum[305]; // 存储石子重量前缀和

int merge_stones(int weights[], int n) {
    stone_sum[0] = 0;
    for (int i = 1; i <= n; ++i) {
        stone_sum[i] = stone_sum[i - 1] + weights[i];
    }
    
    // 初始化区间 DP
    std::fill(&dp_interval[0][0], &dp_interval[0][0] + 305 * 305, 1e9);
    for (int i = 1; i <= n; ++i) dp_interval[i][i] = 0; // 单堆无需合并，代价为 0
    
    // len 表示合并区间的长度 (从 2 开始)
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            int range_sum = stone_sum[j] - stone_sum[i - 1];
            for (int k = i; k < j; ++k) {
                dp_interval[i][j] = std::min(dp_interval[i][j], 
                                             dp_interval[i][k] + dp_interval[k + 1][j] + range_sum);
            }
        }
    }
    return dp_interval[1][n];
}
```

---

## 10. 综合练习题与解析

### 练习题 1：快速幂与高精度模运算
**题目描述**：
计算 $a^b \bmod p$ 的值，其中 $1 \le a, p \le 10^9$，$1 \le b \le 10^{100}$ 且以字符串形式输入。

#### C++11 实现与解析
```cpp
#include <iostream>
#include <string>

// 1. 欧拉定理/大数取模性质：b 对 p - 1 取模
// 此处我们利用大数模拟取余：(b_str) % (p - 1)
long long big_mod(const std::string& b_str, long long m) {
    long long res = 0;
    for (char c : b_str) {
        res = (res * 10 + (c - '0')) % m;
    }
    return res;
}

// 2. 快速幂求 (a^b_mod) % p
long long quick_power(long long a, long long b, long long p) {
    long long res = 1 % p;
    a %= p;
    while (b > 0) {
        if (b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

// 判定 p 是否为质数（若为质数，可用欧拉定理进行幂降模：b = b % (p - 1)）
bool is_prime_test(long long p) {
    if (p < 2) return false;
    for (long long i = 2; i * i <= p; ++i) {
        if (p % i == 0) return false;
    }
    return true;
}

int main() {
    long long a = 3;
    std::string b_str = "1000000000000000000000000000000002"; // 大数
    long long p = 7; // 7 是质数，故 phi(7) = 6
    
    long long b_reduced = 0;
    if (is_prime_test(p)) {
        b_reduced = big_mod(b_str, p - 1); // 指数降模
    } else {
        // 如果 p 不是质数，需使用更广义的欧拉降幂公式。
        // 此处示例仅以 p 为质数进行降模演示。
        b_reduced = big_mod(b_str, p - 1); 
    }
    
    std::cout << "Result: " << quick_power(a, b_reduced, p) << std::endl; // 输出 3^2 % 7 = 2
    return 0;
}
```
**解题思路**：
当指数 $b$ 极其巨大时，直接利用快速幂依然会超时。依据数论中的**欧拉定理**（Euler's Theorem），若 $a$ 与 $p$ 互质，则有：
$$a^{\varphi(p)} \equiv 1 \pmod p \implies a^b \equiv a^{b \bmod \varphi(p)} \pmod p$$
由于 $p=7$ 为质数，有 $\varphi(p) = p - 1 = 6$。因此，我们首先编写 `big_mod` 函数，利用模拟法将巨大的字符串 $b\_str$ 对 $6$ 取余得到 $b\_reduced$，最后在此基础上进行 $O(\log \varphi(p))$ 级别的快速幂运算，极大地降低了算法的时间消耗。

---

### 练习题 2：滑雪（DFS + 记忆化搜索应用）
**题目描述**：
给出一个 $R \times C$ 的滑雪场区域，每个格点代表一个高度。一个人可以向上下左右四个方向下滑，但滑行的格点高度必须严格递减。求在此滑雪场内能滑行的最大路径长度。

#### C++11 实现与解析
```cpp
#include <iostream>
#include <algorithm>

const int MAX_R = 105;
int r, c;
int heights[MAX_R][MAX_R];
int cache[MAX_R][MAX_R]; // 记忆化搜索数组

int s_dx[] = {-1, 1, 0, 0};
int s_dy[] = {0, 0, -1, 1};

// 记忆化 DFS
int dfs_ski(int x, int y) {
    // 若已被计算过，直接返回缓存值
    if (cache[x][y] != -1) return cache[x][y];
    
    int max_path = 1; // 至少可以只滑行当前这一个点
    
    for (int i = 0; i < 4; ++i) {
        int nx = x + s_dx[i];
        int ny = y + s_dy[i];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
            // 只有当高度严格减小时才可以滑动
            if (heights[nx][ny] < heights[x][y]) {
                max_path = std::max(max_path, dfs_ski(nx, ny) + 1);
            }
        }
    }
    
    cache[x][y] = max_path; // 存入缓存
    return max_path;
}

int main() {
    r = 5; c = 5;
    int input_grid[5][5] = {
        {1,  2,  3,  4, 5},
        {16, 17, 18, 19, 6},
        {15, 24, 25, 20, 7},
        {14, 23, 22, 21, 8},
        {13, 12, 11, 10, 9}
    };
    
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            heights[i][j] = input_grid[i][j];
            cache[i][j] = -1; // 初始化标记
        }
    }
    
    int ans = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            ans = std::max(ans, dfs_ski(i, j));
        }
    }
    
    std::cout << "Max skiing path length: " << ans << std::endl; // 输出 25
    return 0;
}
```
**解题思路**：
如果采用普通 DFS 算法直接暴搜所有的递减路径，会产生大量重叠子状态从而导致超时。例如在高度 $20$ 处的解，不管从哪个方向滑过来，只要到 $20$，后面的最大滑行长度就已经是固定且唯一的。
因此，本题采用**记忆化搜索**。定义 `cache[x][y]` 记录从 $(x, y)$ 出发的最大滑动长度。在进入 DFS 递归后，如果该点已被计算，直接 $O(1)$ 读取并返回。这使得每个网格节点实际上只被彻底计算了一次，将原本指数级的暴搜复杂度完美优化到了 $O(R \times C)$ 线性复杂度。

C++11 算法基础讲义

本讲义旨在系统梳理程序设计中常见的算法思想与技术。为契合高性能与低开销的要求，并遵循“尽量避免自定义结构体和指针”的原则，所有代码均采用 C++11 标准，核心数据结构多使用静态一维/多维数组、标准库辅助容器（如 std::vector、std::pair）与独立函数进行设计。

1. 算法概念与描述

1.1 算法基本概念

算法（Algorithm）是解决特定问题的一系列明确、有限的步骤。一个合法的算法应具备以下五个重要特性： 1. 有穷性：算法在执行有限步后必须结束，且每一步都在有穷时间内完成。 2. 确定性：算法中的每一条指令都有确切的含义，无二义性。 3. 可行性：算法中的所有操作都可以通过已经实现的基本运算执行有限次来实现。 4. 输入：有零个或多个输入。 5. 输出：有一个或多个输出。

衡量算法优劣的核心指标为时间复杂度（主要关注最坏情况下的渐进时间复杂度）与空间复杂度，通常使用大 $O$ 符号表示。

1.2 算法描述方法

自然语言：用人类日常语言描述步骤，易理解但容易产生歧义。
流程图：用统一规定的图形符号（如起止框、处理框、判断框等）直观表达逻辑，适合较简单的控制流。
伪代码：介于自然语言与程序设计语言之间，用类似代码的结构化语言来表述算法逻辑，忽略具体语法细节，便于算法的设计与交流。

2. 入门算法

2.1 枚举法 (Enumeration)

枚举法（又称暴力搜索法）是根据问题本身的规律，逐一列举所有可能的解，并根据约束条件判断其是否为合法的解。

优化策略：
- 缩小枚举范围。
- 避免重复计算。

示例：求 $[2, N]$ 之间的所有素数（枚举因子法）

#include <iostream>

// 时间复杂度 O(N * sqrt(N))
bool is_prime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i) { // 仅枚举到 sqrt(n)
        if (n % i == 0) return false;
    }
    return true;
}

void enumerate_primes(int n) {
    for (int i = 2; i <= n; ++i) {
        if (is_prime(i)) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
}

2.2 模拟法 (Simulation)

模拟法是指根据题目描述的规则、过程和步骤，用代码一步步重现该过程，从而得到结果。模拟算法通常不涉及高深的数学推导，但要求代码对细节控制十分精准。

示例：顺时针旋转 $N \times N$ 矩阵 $90^\circ$

设原矩阵为 $A$，旋转后矩阵为 $B$。通过观察几何关系可知，原矩阵的第 $i$ 行第 $j$ 列，旋转后会变成第 $j$ 行第 $N - 1 - i$ 列： $$B[j][N - 1 - i] = A[i][j]$$

#include <iostream>

const int MAX_N = 105;
int mat[MAX_N][MAX_N];
int rotated[MAX_N][MAX_N];

void rotate_matrix(int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            rotated[j][n - 1 - i] = mat[i][j];
        }
    }
}

3. 基础算法

3.1 贪心算法 (Greedy)

贪心算法在求解问题时，总是做出在当前看来是最好的选择。也就是说，它不从整体最优上加以考虑，所做出的仅是局部最优解。 * 适用条件： 1. 贪心选择性质：整体最优解可以通过一系列局部最优（贪心）选择达到。 2. 最优子结构：一个问题的最优解包含其子问题的最优解。 * 证明方法：常见证明有反证法和归纳法（如微调/交换论证 Exchange Argument）。

示例：区间选点问题（选择最少的点，使每个给定闭区间都至少包含一个点）

贪心策略：将所有区间按右端点从小到大排序。每次选择当前未覆盖区间的右端点，以此点覆盖尽可能多的区间。

#include <iostream>
#include <algorithm>
#include <vector>

// 使用 std::pair<int, int> 存储区间，first 为右端点，second 为左端点
// 这样默认排序时会先根据右端点（first）排序
int select_points(std::vector<std::pair<int, int>>& intervals) {
    if (intervals.empty()) return 0;

    std::sort(intervals.begin(), intervals.end());

    int count = 1;
    int last_point = intervals[0].first; // 选择第一个区间的右端点

    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i].second > last_point) { // 如果当前区间的左端点大于上一个选点，说明无法覆盖
            count++;
            last_point = intervals[i].first;    // 在当前区间的右端点放新点
        }
    }
    return count;
}

3.2 递推法 (Recurrence)

递推法是指根据已知的初始状态，通过一个明确的数学递推公式，一步步推导出未知状态。

示例：错排问题 (Derangement)

有 $n$ 个信封和 $n$ 封信，每封信都装错的方案数记为 $D(n)$。 * 公式递推推导： 1. 设第 $n$ 封信放入了第 $i$ 个信封（有 $n-1$ 种选择，假设 $i=1$）。 2. 此时考虑第 1 封信的去向： * 若第 1 封信放入了第 $n$ 个信封，则剩下的 $n-2$ 封信和信封形成错排，方案数为 $D(n-2)$。 * 若第 1 封信没有放入第 $n$ 个信封，则第 1 到第 $n-1$ 封信必须错排放在除第 1 个以外的 $n-1$ 个信封中（将第 $n$ 个信封视作原第 1 封信的“禁区”），方案数为 $D(n-1)$。 3. 综合可得递推公式： $$D(n) = (n - 1) \cdot (D(n - 1) + D(n - 2))$$

long long d[105];

void init_derangement(int n) {
    d[1] = 0;
    d[2] = 1;
    for (int i = 3; i <= n; ++i) {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
    }
}

3.3 递归法 (Recursion)

递归指一个函数直接或间接地调用自身。 * 核心要素： 1. 递归出口（边界条件）：防止无限递归导致栈溢出（Stack Overflow）。 2. 递归递推关系：如何将大问题分解为小问题。

示例：汉诺塔 (Tower of Hanoi) 移动步骤输出

#include <iostream>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        std::cout << "Move disk 1 from " << from << " to " << to << std::endl;
        return;
    }
    hanoi(n - 1, from, aux, to);
    std::cout << "Move disk " << n << " from " << from << " to " << to << std::endl;
    hanoi(n - 1, aux, to, from);
}

3.4 二分法 (Binary Search)

二分法是将区间逐步折半以寻找特定目标或边界的算法。其时间复杂度为 $O(\log N)$。

1. 整数二分模板 (寻找单调序列边界)

处理整数二分时，最棘手的是边界问题。以下提供两套常用模板：

模板 1：寻找符合条件 $Q$ 的左边界（最左侧符合条件的值，如 `std::lower_bound`）

int binary_search_left(int q[], int n, int target) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l) / 2; // 向下取整，避免溢出
        if (q[mid] >= target) {
            r = mid; // 答案在左半边（包含 mid）
        } else {
            l = mid + 1; // 答案在右半边（不含 mid）
        }
    }
    return q[l] == target ? l : -1;
}

模板 2：寻找符合条件 $Q$ 的右边界

int binary_search_right(int q[], int n, int target) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2; // 向上取整，配合 l = mid 防止死循环
        if (q[mid] <= target) {
            l = mid; // 答案在右半边（包含 mid）
        } else {
            r = mid - 1; // 答案在左半边（不含 mid）
        }
    }
    return q[l] == target ? l : -1;
}

2. 实数二分

实数二分无边界整除带来的死循环风险，只需根据精度（$\epsilon$）或循环固定次数进行迭代。

double real_binary_search(double l, double r, double target) {
    const double eps = 1e-7;
    while (r - l > eps) {
        double mid = l + (r - l) / 2.0;
        if (mid * mid >= target) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return l;
}

3.5 倍增法 (Doubling)

倍增法核心思想是“按 2 的幂次递增”，将线性扫描转换为跳跃式扫描，常用于构造 ST 表（解决 RMQ 问题）以及求树的最近公共祖先（LCA）。

示例：ST 表 (Sparse Table) 求解区间最大值

性质：$f[i][j]$ 表示以 $i$ 为起点，长度为 $2^j$ 的区间内的最大值。
状态转移方程： $$f[i][j] = \max(f[i][j - 1], f[i + 2^{j - 1}][j - 1])$$

#include <algorithm>
#include <cmath>

const int MAX_LEN = 100010;
const int LOG_MAX = 20;
int f[MAX_LEN][LOG_MAX];
int lg[MAX_LEN]; // 预处理 log 数组

void init_st(int arr[], int n) {
    // 1. 预处理 log 数组
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    // 2. 初始化第一列
    for (int i = 1; i <= n; ++i) {
        f[i][0] = arr[i];
    }

    // 3. 动态规划递推
    for (int j = 1; j < LOG_MAX; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// 查询 [L, R] 的最大值
int query_st(int l, int r) {
    int k = lg[r - l + 1];
    return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}

4. 算法策略

4.1 前缀和 (Prefix Sum)

前缀和能将区间求和的复杂度由 $O(N)$ 降到 $O(1)$。

1. 一维前缀和

设原数组为 $A$，前缀和数组为 $S$，$S[i] = \sum_{j=1}^{i} A[j]$。 * 区间求和：$[L, R]$ 之间的元素和为 $S[R] - S[L - 1]$。

2. 二维前缀和

设 $S[i][j]$ 表示以 $(1,1)$ 为左上角，$(i,j)$ 为右下角的子矩阵元素和。 * 递推构造公式（容斥原理）： $$S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j]$$ * 子矩阵和查询（求左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 的元素和）： $$\text{Sum} = S[x_2][y_2] - S[x_1 - 1][y_2] - S[x_2][y_1 - 1] + S[x_1 - 1][y_1 - 1]$$

int s2d[MAX_N][MAX_N];

void build_2d_prefix(int a[MAX_N][MAX_N], int row, int col) {
    for (int i = 1; i <= row; ++i) {
        for (int j = 1; j <= col; ++j) {
            s2d[i][j] = s2d[i-1][j] + s2d[i][j-1] - s2d[i-1][j-1] + a[i][j];
        }
    }
}

4.2 差分 (Difference)

差分是前缀和的逆运算，能将区间加减的操作复杂度由 $O(N)$ 降到 $O(1)$。

1. 一维差分

若 $B[i] = A[i] - A[i - 1]$（其中 $A[0] = 0$），则 $B$ 是 $A$ 的差分数组，$A$ 是 $B$ 的前缀和数组。 * 区间加减：若要在原数组区间 $[L, R]$ 上全部加上值 $C$，只需对差分数组操作： $$B[L] \leftarrow B[L] + C, \quad B[R + 1] \leftarrow B[R + 1] - C$$

2. 二维差分

对以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩阵全部加上值 $C$，操作差分数组 $D$ 的方法为： $$D[x_1][y_1] += C, \quad D[x_2+1][y_1] -= C, \quad D[x_1][y_2+1] -= C, \quad D[x_2+1][y_2+1] += C$$

int d2d[MAX_N][MAX_N];

void add_2d_diff(int x1, int y1, int x2, int y2, int c) {
    d2d[x1][y1] += c;
    d2d[x2 + 1][y1] -= c;
    d2d[x1][y2 + 1] -= c;
    d2d[x2 + 1][y2 + 1] += c;
}

// 恢复原矩阵：对差分矩阵求一次二维前缀和即可

5. 数值处理（高精度运算）

当数值超出 long long 的表示范围（例如达到 $10^{100}$ 甚至更高）时，需要用数组来模拟手算过程。在代码中，我们使用 std::vector<int> 逆序存储大数（即个位存储在 vector[0]，便于最高位进位时在尾部直接 push_back）。

5.1 高精度加法

#include <vector>
#include <string>

std::vector<int> add_high_precision(const std::vector<int>& A, const std::vector<int>& B) {
    std::vector<int> C;
    int t = 0; // 进位
    for (size_t i = 0; i < A.size() || i < B.size(); ++i) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}

5.2 高精度减法

// 辅助判定 A >= B
bool compare_high_precision(const std::vector<int>& A, const std::vector<int>& B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; --i) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

std::vector<int> sub_high_precision(const std::vector<int>& A, const std::vector<int>& B) {
    std::vector<int> C;
    int t = 0; // 借位
    for (size_t i = 0; i < A.size(); ++i) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    // 去除前导 0，但保证至少剩下一个数
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

5.3 高精度乘法（高精度 $\times$ 低精度）

std::vector<int> mul_high_precision(const std::vector<int>& A, int b) {
    std::vector<int> C;
    int t = 0; // 乘积与进位
    for (size_t i = 0; i < A.size() || t; ++i) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前导0
    return C;
}

5.4 高精度除法（高精度 $\div$ 低精度）

#include <algorithm>

// 返回商，r 作为引用传回余数
std::vector<int> div_high_precision(const std::vector<int>& A, int b, int& r) {
    std::vector<int> C;
    r = 0; // 余数
    // 除法从最高位开始算
    for (int i = A.size() - 1; i >= 0; --i) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    std::reverse(C.begin(), C.end()); // 翻转以保持低位在前
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

6. 排序算法

此处实现经典的四种初等排序，并统一分析其复杂度与稳定性。

算法名称	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$O(N)$（带优化）	$O(N^2)$	$O(1)$	稳定
选择排序	$O(N^2)$	$O(N^2)$	$O(1)$	不稳定
插入排序	$O(N)$	$O(N^2)$	$O(1)$	稳定
计数排序	$O(N + K)$	$O(N + K)$	$O(N + K)$	稳定

6.1 冒泡排序 (Bubble Sort)

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool has_swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                has_swapped = true;
            }
        }
        if (!has_swapped) break; // 若某趟未发生交换，说明已有序
    }
}

6.2 选择排序 (Selection Sort)

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        std::swap(arr[i], arr[min_idx]);
    }
}

6.3 插入排序 (Insertion Sort)

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int val = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > val) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = val;
    }
}

6.4 计数排序 (Counting Sort)

#include <cstring>

const int K_RANGE = 100010; // 假设数据范围非负且不大于该值
int count_arr[K_RANGE];
int temp_arr[MAX_LEN];

void counting_sort(int arr[], int n) {
    std::memset(count_arr, 0, sizeof(count_arr));

    // 1. 统计频率
    for (int i = 0; i < n; ++i) {
        count_arr[arr[i]]++;
    }

    // 2. 累加频率，使其表示位置
    for (int i = 1; i < K_RANGE; ++i) {
        count_arr[i] += count_arr[i - 1];
    }

    // 3. 逆序构建以保持稳定性
    for (int i = n - 1; i >= 0; --i) {
        temp_arr[count_arr[arr[i]] - 1] = arr[i];
        count_arr[arr[i]]--;
    }

    // 4. 写回原数组
    for (int i = 0; i < n; ++i) {
        arr[i] = temp_arr[i];
    }
}

7. 搜索算法与 8. 图论基础算法

7.1 DFS（深度优先搜索）与 BFS（广度优先搜索）在迷宫中的应用

我们使用平行静态数组记录迷宫状态与路径信息，完全避开自定义点结构体。

#include <queue>
#include <utility>

const int g_rows = 5, g_cols = 5;
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 1, 0},
    {1, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};
bool visited[5][5];

// 移动方向：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 1. DFS 寻找任意可行通路
bool dfs_maze(int x, int y) {
    if (x == g_rows - 1 && y == g_cols - 1) return true; // 到达终点
    visited[x][y] = true;

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < g_rows && ny >= 0 && ny < g_cols) {
            if (!visited[nx][ny] && maze[nx][ny] == 0) {
                if (dfs_maze(nx, ny)) return true;
            }
        }
    }
    return false;
}

// 2. BFS 寻找最短路径步数
int bfs_maze_steps() {
    std::queue<std::pair<int, int>> q; // 存储坐标 {x, y}
    int dist[5][5];                    // 记录距离
    std::fill(&dist[0][0], &dist[0][0] + 25, -1);

    q.push(std::make_pair(0, 0));
    dist[0][0] = 0;

    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        int cx = curr.first;
        int cy = curr.second;

        if (cx == g_rows - 1 && cy == g_cols - 1) return dist[cx][cy];

        for (int i = 0; i < 4; ++i) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx >= 0 && nx < g_rows && ny >= 0 && ny < g_cols) {
                if (dist[nx][ny] == -1 && maze[nx][ny] == 0) {
                    dist[nx][ny] = dist[cx][cy] + 1;
                    q.push(std::make_pair(nx, ny));
                }
            }
        }
    }
    return -1;
}

7.2 图的静态 DFS 与 BFS

使用上一讲的链式前向星（静态邻接表）实现。

// 链式前向星全局变量
const int N_V = 10005;
const int M_E = 100005;
int head[N_V], to_node[M_E], next_edge[M_E], edge_cnt;
bool graph_vis[N_V];

// 图的 DFS
void dfs_graph(int u) {
    graph_vis[u] = true;
    for (int i = head[u]; i != -1; i = next_edge[i]) {
        int v = to_node[i];
        if (!graph_vis[v]) {
            dfs_graph(v);
        }
    }
}

// 图的 BFS
void bfs_graph(int start) {
    std::queue<int> q;
    q.push(start);
    graph_vis[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = next_edge[i]) {
            int v = to_node[i];
            if (!graph_vis[v]) {
                graph_vis[v] = true;
                q.push(v);
            }
        }
    }
}

7.3 泛洪算法 (Flood Fill)

泛洪算法常用于寻找网格图中的连通分量个数（如求孤岛、连通水域）。

int grid[5][5]; // 假设非 0 表示有障碍，0 表示平地
bool fill_vis[5][5];

void flood_fill(int x, int y) {
    fill_vis[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
            if (!fill_vis[nx][ny] && grid[nx][ny] == 0) {
                flood_fill(nx, ny);
            }
        }
    }
}

int count_components() {
    int count = 0;
    std::fill(&fill_vis[0][0], &fill_vis[0][0] + 25, false);
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            if (!fill_vis[i][j] && grid[i][j] == 0) {
                count++;
                flood_fill(i, j); // 淹没所有与其连通的节点
            }
        }
    }
    return count;
}

9. 动态规划 (Dynamic Programming)

动态规划思想主要是通过将问题分解为相互重叠的子问题，并通过存储子问题的解来避免重复计算，常适用于具有最优子结构和重叠子问题性质的场景。

9.1 一维动态规划（最长上升子序列 LIS）

状态设计：$dp[i]$ 表示以 $arr[i]$ 结尾的最长上升子序列的长度。
状态转移方程： $$dp[i] = \max(1, dp[j] + 1) \quad (\text{其中 } 0 \le j < i \text{ 且 } arr[j] < arr[i])$$

#include <algorithm>

int dp_lis[1005];

int get_lis_length(int arr[], int n) {
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        dp_lis[i] = 1; // 自身能形成一个长度为 1 的子序列
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) {
                dp_lis[i] = std::max(dp_lis[i], dp_lis[j] + 1);
            }
        }
        max_len = std::max(max_len, dp_lis[i]);
    }
    return max_len;
}

9.2 背包类型 DP

1. 0/1 背包问题（滚动数组优化空间）

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的重量是 $w[i]$，价值是 $v[i]$。每种物品仅有一件。 * 状态设计：$dp[j]$ 表示在容量为 $j$ 时的最大价值。 * 转移方程推导：原始转移方程：$dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])$。在降维优化时，为确保计算 $dp[j]$ 时，使用的是上一轮的 $dp[j-w[i]]$（防止同一件物品被多次放入），内层循环必须逆序。 $$dp[j] = \max(dp[j], dp[j - w[i]] + v[i])$$

int dp_01[10005]; // 大小为最大背包容量

int knapsack_01(int w[], int v[], int n, int bag_v) {
    std::fill(dp_01, dp_01 + bag_v + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = bag_v; j >= w[i]; --j) { // 逆序
            dp_01[j] = std::max(dp_01[j], dp_01[j - w[i]] + v[i]);
        }
    }
    return dp_01[bag_v];
}

2. 完全背包问题

每种物品有无限多件。 * 转移方程：由于物品可以被多次选择，内层循环必须正序，从而可以在当前决策中累加该物品的多次贡献。 $$dp[j] = \max(dp[j], dp[j - w[i]] + v[i])$$

int dp_complete[10005];

int knapsack_complete(int w[], int v[], int n, int bag_v) {
    std::fill(dp_complete, dp_complete + bag_v + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = w[i]; j <= bag_v; ++j) { // 正序
            dp_complete[j] = std::max(dp_complete[j], dp_complete[j - w[i]] + v[i]);
        }
    }
    return dp_complete[bag_v];
}

9.3 区间类型 DP（经典：合并石子）

设有 $N$ 堆石子排成一排，每次只能合并相邻的两堆，合并的代价为两堆石子的重量之和。求将所有石子合并成一堆的最小代价。

状态定义：$dp[i][j]$ 表示合并第 $i$ 堆到第 $j$ 堆石子的最小代价。
状态转移推导：合并区间 $[i, j]$，可以看作是先把其分为两部分 $[i, k]$ 与 $[k + 1, j]$，然后再进行一次大合并。 $$dp[i][j] = \min_{i \le k < j}(dp[i][k] + dp[k + 1][j]) + \text{sum}(i, j)$$ 其中 $\text{sum}(i, j)$ 可通过前缀和 $O(1)$ 获得。
计算顺序：由于大区间的解依赖小区间的解，必须按区间长度从短到长开始循环递推。

int dp_interval[305][305];
int stone_sum[305]; // 存储石子重量前缀和

int merge_stones(int weights[], int n) {
    stone_sum[0] = 0;
    for (int i = 1; i <= n; ++i) {
        stone_sum[i] = stone_sum[i - 1] + weights[i];
    }

    // 初始化区间 DP
    std::fill(&dp_interval[0][0], &dp_interval[0][0] + 305 * 305, 1e9);
    for (int i = 1; i <= n; ++i) dp_interval[i][i] = 0; // 单堆无需合并，代价为 0

    // len 表示合并区间的长度 (从 2 开始)
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            int range_sum = stone_sum[j] - stone_sum[i - 1];
            for (int k = i; k < j; ++k) {
                dp_interval[i][j] = std::min(dp_interval[i][j], 
                                             dp_interval[i][k] + dp_interval[k + 1][j] + range_sum);
            }
        }
    }
    return dp_interval[1][n];
}

10. 综合练习题与解析

练习题 1：快速幂与高精度模运算

题目描述：计算 $a^b \bmod p$ 的值，其中 $1 \le a, p \le 10^9$，$1 \le b \le 10^{100}$ 且以字符串形式输入。

C++11 实现与解析

#include <iostream>
#include <string>

// 1. 欧拉定理/大数取模性质：b 对 p - 1 取模
// 此处我们利用大数模拟取余：(b_str) % (p - 1)
long long big_mod(const std::string& b_str, long long m) {
    long long res = 0;
    for (char c : b_str) {
        res = (res * 10 + (c - '0')) % m;
    }
    return res;
}

// 2. 快速幂求 (a^b_mod) % p
long long quick_power(long long a, long long b, long long p) {
    long long res = 1 % p;
    a %= p;
    while (b > 0) {
        if (b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

// 判定 p 是否为质数（若为质数，可用欧拉定理进行幂降模：b = b % (p - 1)）
bool is_prime_test(long long p) {
    if (p < 2) return false;
    for (long long i = 2; i * i <= p; ++i) {
        if (p % i == 0) return false;
    }
    return true;
}

int main() {
    long long a = 3;
    std::string b_str = "1000000000000000000000000000000002"; // 大数
    long long p = 7; // 7 是质数，故 phi(7) = 6

    long long b_reduced = 0;
    if (is_prime_test(p)) {
        b_reduced = big_mod(b_str, p - 1); // 指数降模
    } else {
        // 如果 p 不是质数，需使用更广义的欧拉降幂公式。
        // 此处示例仅以 p 为质数进行降模演示。
        b_reduced = big_mod(b_str, p - 1); 
    }

    std::cout << "Result: " << quick_power(a, b_reduced, p) << std::endl; // 输出 3^2 % 7 = 2
    return 0;
}

解题思路：当指数 $b$ 极其巨大时，直接利用快速幂依然会超时。依据数论中的欧拉定理（Euler's Theorem），若 $a$ 与 $p$ 互质，则有： $$a^{\varphi(p)} \equiv 1 \pmod p \implies a^b \equiv a^{b \bmod \varphi(p)} \pmod p$$ 由于 $p=7$ 为质数，有 $\varphi(p) = p - 1 = 6$。因此，我们首先编写 big_mod 函数，利用模拟法将巨大的字符串 $b_str$ 对 $6$ 取余得到 $b_reduced$，最后在此基础上进行 $O(\log \varphi(p))$ 级别的快速幂运算，极大地降低了算法的时间消耗。

练习题 2：滑雪（DFS + 记忆化搜索应用）

题目描述：给出一个 $R \times C$ 的滑雪场区域，每个格点代表一个高度。一个人可以向上下左右四个方向下滑，但滑行的格点高度必须严格递减。求在此滑雪场内能滑行的最大路径长度。

C++11 实现与解析

#include <iostream>
#include <algorithm>

const int MAX_R = 105;
int r, c;
int heights[MAX_R][MAX_R];
int cache[MAX_R][MAX_R]; // 记忆化搜索数组

int s_dx[] = {-1, 1, 0, 0};
int s_dy[] = {0, 0, -1, 1};

// 记忆化 DFS
int dfs_ski(int x, int y) {
    // 若已被计算过，直接返回缓存值
    if (cache[x][y] != -1) return cache[x][y];

    int max_path = 1; // 至少可以只滑行当前这一个点

    for (int i = 0; i < 4; ++i) {
        int nx = x + s_dx[i];
        int ny = y + s_dy[i];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
            // 只有当高度严格减小时才可以滑动
            if (heights[nx][ny] < heights[x][y]) {
                max_path = std::max(max_path, dfs_ski(nx, ny) + 1);
            }
        }
    }

    cache[x][y] = max_path; // 存入缓存
    return max_path;
}

int main() {
    r = 5; c = 5;
    int input_grid[5][5] = {
        {1,  2,  3,  4, 5},
        {16, 17, 18, 19, 6},
        {15, 24, 25, 20, 7},
        {14, 23, 22, 21, 8},
        {13, 12, 11, 10, 9}
    };

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            heights[i][j] = input_grid[i][j];
            cache[i][j] = -1; // 初始化标记
        }
    }

    int ans = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            ans = std::max(ans, dfs_ski(i, j));
        }
    }

    std::cout << "Max skiing path length: " << ans << std::endl; // 输出 25
    return 0;
}

解题思路：如果采用普通 DFS 算法直接暴搜所有的递减路径，会产生大量重叠子状态从而导致超时。例如在高度 $20$ 处的解，不管从哪个方向滑过来，只要到 $20$，后面的最大滑行长度就已经是固定且唯一的。因此，本题采用记忆化搜索。定义 cache[x][y] 记录从 $(x, y)$ 出发的最大滑动长度。在进入 DFS 递归后，如果该点已被计算，直接 $O(1)$ 读取并返回。这使得每个网格节点实际上只被彻底计算了一次，将原本指数级的暴搜复杂度完美优化到了 $O(R \times C)$ 线性复杂度。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

入门组大纲2.1.4 算法

C++11 算法基础讲义

1. 算法概念与描述

1.1 算法基本概念

1.2 算法描述方法

2. 入门算法

2.1 枚举法 (Enumeration)

示例：求 $[2, N]$ 之间的所有素数（枚举因子法）

2.2 模拟法 (Simulation)

示例：顺时针旋转 $N \times N$ 矩阵 $90^\circ$

3. 基础算法

3.1 贪心算法 (Greedy)

示例：区间选点问题（选择最少的点，使每个给定闭区间都至少包含一个点）

3.2 递推法 (Recurrence)

示例：错排问题 (Derangement)

3.3 递归法 (Recursion)

示例：汉诺塔 (Tower of Hanoi) 移动步骤输出

3.4 二分法 (Binary Search)

1. 整数二分模板 (寻找单调序列边界)

模板 1：寻找符合条件 $Q$ 的左边界（最左侧符合条件的值，如 std::lower_bound）

模板 2：寻找符合条件 $Q$ 的右边界

2. 实数二分

3.5 倍增法 (Doubling)

示例：ST 表 (Sparse Table) 求解区间最大值

4. 算法策略

4.1 前缀和 (Prefix Sum)

1. 一维前缀和

2. 二维前缀和

4.2 差分 (Difference)

1. 一维差分

2. 二维差分

5. 数值处理（高精度运算）

5.1 高精度加法

5.2 高精度减法

5.3 高精度乘法（高精度 $\times$ 低精度）

5.4 高精度除法（高精度 $\div$ 低精度）

6. 排序算法

6.1 冒泡排序 (Bubble Sort)

6.2 选择排序 (Selection Sort)

6.3 插入排序 (Insertion Sort)

6.4 计数排序 (Counting Sort)

7. 搜索算法 与 8. 图论基础算法

7.1 DFS（深度优先搜索）与 BFS（广度优先搜索）在迷宫中的应用

7.2 图的静态 DFS 与 BFS

7.3 泛洪算法 (Flood Fill)

9. 动态规划 (Dynamic Programming)

9.1 一维动态规划（最长上升子序列 LIS）

9.2 背包类型 DP

1. 0/1 背包问题（滚动数组优化空间）

2. 完全背包问题

9.3 区间类型 DP（经典：合并石子）

10. 综合练习题与解析

练习题 1：快速幂与高精度模运算

C++11 实现与解析

练习题 2：滑雪（DFS + 记忆化搜索应用）

C++11 实现与解析

模板 1：寻找符合条件 $Q$ 的左边界（最左侧符合条件的值，如 `std::lower_bound`）

7. 搜索算法与 8. 图论基础算法