一 高精度

1.1 高精度加法

话不多说，上代码！

#include<bits/stdc++.h> 
using namespace std;

int main() {
    string num1_str, num2_str; // 存储输入的两个大数字符串
    int num1_arr[1000] = {0}, num2_arr[1000] = {0}, result_arr[1001] = {0}; // 数组用于存储数字的每一位
    int i, len1, len2, max_len; // 变量声明：循环计数器，两个数字的长度，最大长度

    // 输入两个大数
    cin >> num1_str >> num2_str;
    
    // 获取两个数字的长度
    len1 = num1_str.size();
    len2 = num2_str.size();
    // 确定两个数字中较长的长度
    max_len = max(len1, len2); 

    // 将第一个数字字符串转换为整数数组（逆序存储：个位在索引0位置）
    for (i = 0; i < len1; i++) 
    {
        num1_arr[len1 - 1 - i] = num1_str[i] - '0'; // 字符转数字并逆序存储
    }
    
    // 将第二个数字字符串转换为整数数组（同样逆序存储）
    for (i = 0; i < len2; i++) 
    {
        num2_arr[len2 - 1 - i] = num2_str[i] - '0'; // 字符转数字并逆序存储
    }

    // 逐位相加并处理进位
    for (i = 0; i < max_len; i++) 
    {
        // 将两个数字的当前位相加（包括可能的进位）
        result_arr[i] += num1_arr[i] + num2_arr[i]; 
        
        // 如果当前位的结果大于等于10，需要进位
        if (result_arr[i] >= 10) 
        { 
            // 将进位加到下一位
            result_arr[i + 1] += result_arr[i] / 10;
            // 保留当前位的个位数
            result_arr[i] %= 10;
        }
    }

    // 检查最高位是否有进位
    if (result_arr[max_len] > 0) {
        max_len++; // 如果有进位，结果长度增加1
    }

    // 输出结果（从最高位到最低位）
    for (i = max_len - 1; i >= 0; i--) {
       cout << result_arr[i]; // 逆序输出，恢复正常的数字顺序
    }

    return 0;
}

1.2 高精度减法

#include<bits/stdc++.h> 
using namespace std;

// 比较两个大数（逆序存储）的大小，判断A是否大于等于B
bool compare(const vector<int>& A, const 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; // 两数相等
}

// 高精度减法函数（假设A >= B，且A和B均为逆序存储的非负整数）
vector<int> subtract(const vector<int>& A, const vector<int>& B) {
    vector<int> C; // 存储结果的动态数组
    int borrow = 0; // 借位标志，0表示无借位，1表示有借位

    // 逐位相减
    for (int i = 0; i < A.size(); i++) {
        int current = A[i] - borrow; // 减去上一位的借位
        if (i < B.size()) current -= B[i]; // 如果B还有位数，减去B的当前位
        /* 
         * (current + 10) % 10 巧妙处理两种情况：
         * 1. 若current >= 0，结果为current，无需额外处理
         * 2. 若current < 0，结果为current + 10（借位后的值）
         */
        C.push_back((current + 10) % 10); 
        borrow = (current < 0) ? 1 : 0; // 若当前位不足，设置借位标志
    }

    // 去除结果的前导零（保留至少一位，例如结果0）
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

int main() {
    string num1, num2;
    cin >> num1 >> num2;

    // 将字符串逆序存储为整数数组（个位在索引0位置）
    vector<int> A, B;
    for (int i = num1.size() - 1; i >= 0; i--) A.push_back(num1[i] - '0');
    for (int i = num2.size() - 1; i >= 0; i--) B.push_back(num2[i] - '0');

    // 处理并输出结果
    if (compare(A, B)) { // A >= B时，直接计算A - B
        vector<int> result = subtract(A, B);
        for (int i = result.size() - 1; i >= 0; i--) cout << result[i];
    } else { // A < B时，计算B - A并输出负号
        vector<int> result = subtract(B, A);
        cout << '-';
        for (int i = result.size() - 1; i >= 0; i--) cout << result[i];
    }
    return 0;
}

1.3高精度乘法

#include<bits/stdc++.h> 
using namespace std;

string multiply(string num1, string num2) {
    // 处理特殊情况：如果任一数为0，乘积直接为0
    if (num1 == "0" || num2 == "0") {
        return "0";
    }
    
    int n1 = num1.size();
    int n2 = num2.size();
    // 结果的最大可能长度为 n1 + n2
    vector<int> result(n1 + n2, 0);
    
    // 将两个数字逆序存储（个位在索引0位置）
    vector<int> a(n1), b(n2);
    for (int i = 0; i < n1; i++) {
        a[i] = num1[n1 - 1 - i] - '0'; // 字符转数字并逆序存储
    }
    for (int i = 0; i < n2; i++) {
        b[i] = num2[n2 - 1 - i] - '0'; // 字符转数字并逆序存储
    }
    
    // 模拟手工乘法：逐位相乘并累加
    for (int i = 0; i < n2; i++) {     // 遍历第二个数的每一位
        for (int j = 0; j < n1; j++) { // 遍历第一个数的每一位
            // 当前位的乘积应放在结果的 i+j 位置
            // 这里先累加到结果数组，后续统一处理进位
            result[i + j] += a[j] * b[i];
        }
    }
    
    // 统一处理所有进位
    for (int i = 0; i < n1 + n2 - 1; i++) {
        result[i + 1] += result[i] / 10; // 进位加到高位
        result[i] %= 10;                 // 当前位只保留个位数
    }
    
    // 转换为字符串并去除前导零
    string resultStr;
    for (int i = result.size() - 1; i >= 0; i--) {
        // 跳过最高位可能存在的零（但保留最后一位即使是零）
        if (i == result.size() - 1 && result[i] == 0) {
            continue;
        }
        resultStr += to_string(result[i]);
    }
    
    return resultStr;
}

int main() {
    string num1, num2;
    cin >> num1 >> num2;
    
    string product = multiply(num1, num2);
    cout << product << endl;
    
    return 0;
}

高精度除法不常考，并且较难，不易理解

二 搜索算法

提示，本章所用的两个算法大多数出现在图中，故而均已图为示例

2.1 深度搜索（dfs）

顾名思义，深度优先先对当前节点找下一个节点，直至到头；到头后回溯到前一个节点再次进行深度搜索

代码：

#include<bits/stdc++.h> 
using namespace std;

void dfsRecursive(const vector<vector<int>>& graph, int node, vector<bool>& visited) {
    visited[node] = true;           // 标记当前节点已访问
    cout << node << " ";             // 处理节点（如打印）
    
    for (int neighbor : graph[node]) { // 遍历所有邻居
        if (!visited[neighbor]) {      // 如果邻居未访问
            dfsRecursive(graph, neighbor, visited); // 递归访问
        }
    }
}

void dfsIterative(const vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false); // 访问标记数组
    stack<int> stk;                           // 显式栈
    stk.push(start);                          // 起点入栈
    
    while (!stk.empty()) {
        int node = stk.top();
        stk.pop();
        
        if (!visited[node]) {
            visited[node] = true;             // 标记已访问
            cout << node << " ";               // 处理节点
            
            // 将未访问邻居逆序入栈（保证顺序性）
            for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
                if (!visited[*it]) {
                    stk.push(*it);
                }
            }
        }
    }
}

int main() {
    // 图的邻接表表示（无向图示例）
    vector<vector<int>> graph = {
        {1, 2},     // 节点0的邻居
        {0, 3, 4},   // 节点1的邻居
        {0, 5},      // 节点2的邻居
        {1},         // 节点3的邻居
        {1},         // 节点4的邻居
        {2}          // 节点5的邻居
    };
    
    vector<bool> visited_recursive(graph.size(), false);
    dfsRecursive(graph, 0, visited_recursive);
    cout << endl;
    return 0;
}

2.2 广度优先bfs

不同于dfs，bfs优先查找当前节点的相邻节点，为了保证搜索顺序，使用队列来记录待查找的节点

代码：

#include<bits/stdc++.h> 
using namespace std;

// 广度优先搜索函数
void bfs(int start, const vector<vector<int>>& graph) {
    int n = graph.size(); // 图中节点数量
    vector<bool> visited(n, false); // 记录节点是否被访问过
    queue<int> q; // 辅助队列，用于BFS

    // 从起始节点开始
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int current = q.front(); // 取出队列首部的节点
        q.pop();
        
        cout << current << " "; // 处理当前节点（这里简单打印）
        
        // 遍历当前节点的所有邻居节点
        for (int neighbor : graph[current]) {
            // 如果邻居节点未被访问，标记并加入队列
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 图的邻接表表示示例
    // 这里以一个有6个节点的图为例
    vector<vector<int>> graph = {
        {1, 2},    // 节点0的邻居是节点1和2
        {0, 3, 4}, // 节点1的邻居是节点0、3、4
        {0, 4, 5}, // 节点2的邻居是节点0、4、5
        {1},       // 节点3的邻居是节点1
        {1, 2},    // 节点4的邻居是节点1和2
        {2}        // 节点5的邻居是节点2
    };

    bfs(0, graph); // 从节点0开始进行BFS遍历
    cout << endl;

    return 0;
}

三 最短路径算法