1.P8744 左孩子右兄弟

代码注释与原理说明

CPP

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

int n, x;          // n: 节点总数, x: 临时变量用于输入父节点
int f[100005];      // f[i]: 存储以节点i为根的子树中，从i开始的最长链权值（链上所有节点的子节点个数之和）
vector<int> v[100005]; // 邻接表，v[i]存储节点i的所有子节点

void dfs(int x) {
    // 遍历当前节点x的所有子节点
    for (auto i : v[x]) {
        dfs(i);  // 递归处理子节点i
        // 更新f[x]: 取所有子节点f[i]的最大值
        f[x] = max(f[x], f[i]);
    }
    // 将当前节点的子节点个数累加到f[x]中
    f[x] += v[x].size(); 
}

int main() {
    scanf("%d", &n);  // 输入节点总数n
    // 构建树结构：节点1为根，节点2~n的父节点
    for (int i = 2; i <= n; i++) {
        scanf("%d", &x);     // 输入节点i的父节点x
        v[x].push_back(i);   // 将i添加为x的子节点
    }
    dfs(1);          // 从根节点1开始DFS遍历
    cout << f[1] << endl; // 输出结果：从根开始的最长链权值
    return 0;
}

算法原理

问题目标

计算树中从根节点出发的最长链权值，其中链的权值定义为：链上每个节点的子节点个数之和。

核心思想

树形DP（动态规划）：通过DFS后序遍历，自底向上计算每个节点的状态值。
状态定义：f[x] 表示以节点 x 为根的子树中，从 x 开始向下延伸的最长链的权值（链上所有节点的子节点个数之和）。
关键观察：
- 对于叶子节点（无子节点），f[x] = 0（因为 v[x].size() = 0）。
- 对于非叶子节点，其值由两部分组成：
  1. 子节点的最优值：所有子节点 i 的 f[i] 的最大值（即选择最优分支）。
  2. 当前节点的贡献：当前节点 x 的子节点个数（v[x].size()）。

计算过程

DFS遍历：从根节点开始递归遍历子树。
递归子节点：对每个子节点递归调用 dfs，先计算子节点的 f[i]。
更新当前节点：
- 遍历所有子节点，找出最大的 f[i]。
- 将 f[x] 设置为该最大值加上当前节点的子节点个数。
输出结果：根节点的 f[1] 即为所求最长链权值。

示例分析

考虑树结构：

CPP

节点4/5（叶子）：f[4] = f[5] = 0（无子节点）。
节点2：子节点为 {4,5}，max(f[4], f[5]) = 0，f[2] = 0 + 2 = 2（子节点个数为2）。
节点3：f[3] = 0（无子节点）。
节点1：子节点为 {2,3}，max(f[2], f[3]) = 2，f[1] = 2 + 2 = 4（子节点个数为2）。

最长链：1 → 2，权值 = 节点1的子节点数（2） + 节点2的子节点数（2） = 4。

时间复杂度

DFS遍历：每个节点访问一次，每条边访问一次。
总时间复杂度：(O(n))，其中 (n) 为节点数。

2.P1030 求先序排列

代码注释与原理说明

CPP

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

char s1[10], s2[10]; // s1: 中序遍历序列, s2: 后序遍历序列
int len;             // 二叉树节点总数

// 在中序序列s1中查找字符ch的位置
inline int find(char ch) {
    for(int i = 0; i < len; i++) {
        if(s1[i] == ch) 
            return i; // 返回字符在中序序列中的索引
    }
    return -1; // 理论上不会执行到这里（字符必定存在）
}

// 递归重建二叉树并输出前序遍历
// l1, r1: 当前子树在中序序列中的区间[l1, r1]
// l2, r2: 当前子树在后序序列中的区间[l2, r2]
void dfs(int l1, int r1, int l2, int r2) {
    // 从后序序列中获取当前子树的根节点（后序最后一个元素）
    char root = s2[r2];
    // 输出根节点（前序遍历：根左右，先输出根）
    cout << root;
    
    // 在中序序列中查找根节点的位置
    int m = find(root);
    
    // 计算左子树节点数
    int left_size = m - l1;
    // 计算右子树节点数
    int right_size = r1 - m;
    
    // 递归处理左子树（如果存在）
    if(left_size > 0) { // m > l1 表示有左子树
        // 中序左子树区间：[l1, m-1]
        // 后序左子树区间：[l2, l2+left_size-1]
        dfs(l1, m-1, l2, l2+left_size-1);
    }
    
    // 递归处理右子树（如果存在）
    if(right_size > 0) { // m < r1 表示有右子树
        // 中序右子树区间：[m+1, r1]
        // 后序右子树区间：[l2+left_size, r2-1]
        dfs(m+1, r1, l2+left_size, r2-1);
    }
}

int main() {
    cin >> s1; // 输入中序遍历序列
    cin >> s2; // 输入后序遍历序列
    len = strlen(s1); // 获取序列长度
    
    // 从完整序列区间开始递归
    dfs(0, len-1, 0, len-1);
    
    return 0;
}

算法原理

问题目标

已知二叉树的中序遍历序列和后序遍历序列，输出其前序遍历序列。

核心思想

二叉树遍历性质：
- 后序遍历：最后一个元素是当前子树的根节点
- 中序遍历：根节点左侧是左子树，右侧是右子树
- 前序遍历：第一个元素是根节点（根→左→右）
递归重建：
- 从后序序列获取根节点
- 在中序序列中定位根节点位置
- 根据根节点位置划分左右子树
- 递归处理左右子树
- 按根→左→右顺序输出（前序）

关键步骤

获取根节点：

CPP

char root = s2[r2]; // 后序序列的最后一个元素

定位根节点在中序序列的位置：

CPP

int m = find(root); // 返回根节点在中序序列的索引

计算子树大小：

CPP

int left_size = m - l1;  // 左子树节点数
int right_size = r1 - m; // 右子树节点数

递归处理子树：
- 左子树：
  CPP
```
dfs(l1, m-1, l2, l2+left_size-1);
```
  - 中序区间：[l1, m-1]
  - 后序区间：[l2, l2+left_size-1]
- 右子树：
  CPP
```
dfs(m+1, r1, l2+left_size, r2-1);
```
  - 中序区间：[m+1, r1]
  - 后序区间：[l2+left_size, r2-1]

递归终止条件

当子树大小为0时（left_size == 0 或 right_size == 0），自动结束递归

示例分析

假设输入：

CPP

中序 s1 = "DBEAFC"
后序 s2 = "DEBFCA"

重建过程：

后序最后一个元素 'A' 是根
在中序中找到 'A' 的位置3（0-based）
- 左子树中序："DBE"（索引0-2）
- 右子树中序："FC"（索引4-5）
左子树后序："DEB"（长度=3）
右子树后序："FC"（长度=2）
输出前序："ABDECF"

时间复杂度

最坏情况： $O(n^2)$ （树退化成链，每次查找需要 $O(n)$ ）
优化方案：用哈希表预存中序位置，可优化到 $O(n)$

优化版本

CPP

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

char s1[10], s2[10];
int len;
unordered_map<char, int> pos_map; // 中序位置哈希表

void dfs(int l1, int r1, int l2, int r2) {
    char root = s2[r2];
    cout << root;
    
    int m = pos_map[root]; // O(1)查找
    
    int left_size = m - l1;
    int right_size = r1 - m;
    
    if(left_size > 0)
        dfs(l1, m-1, l2, l2+left_size-1);
    if(right_size > 0)
        dfs(m+1, r1, l2+left_size, r2-1);
}

int main() {
    cin >> s1 >> s2;
    len = strlen(s1);
    
    // 预存中序位置
    for(int i = 0; i < len; i++) {
        pos_map[s1[i]] = i;
    }
    
    dfs(0, len-1, 0, len-1);
    return 0;
}

3.P4305 不重复数字

CPP

#include <cstdio>      // 标准输入输出库（包含scanf/printf）
#include <unordered_map> // 哈希表容器
using namespace std;

int T, n, x; // 全局变量：
             // T - 测试用例数量
             // n - 每个测试用例的数字个数
             // x - 临时存储读取的数字

unordered_map<int, bool> s; // 哈希表用于记录数字是否已出现
                            // key: 整数值
                            // value: 是否出现过（true/false）

void work() {
    s.clear();  // 清空哈希表（关键：每组测试前重置状态）
    scanf("%d", &n); // 读取当前测试用例的数字个数
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x); // 读取每个数字
        
        // 如果当前数字未出现过
        if (!s[x]) {
            printf("%d ", x); // 输出该数字（保留首次出现的顺序）
            s[x] = true;      // 标记为已出现
        }
    }
    puts(""); // 输出换行（结束当前测试用例的输出）
}

int main() {
    scanf("%d", &T); // 读取测试用例总数
    
    // 循环处理每个测试用例
    while (T--) {
        work();
    }
    
    return 0;
}

代码原理详解：

去重算法：
- 核心思想：利用哈希表记录元素出现状态
- 处理流程：
  1. 读取新数字 x
  2. 检查 s[x] 标记：
    - 若未标记（首次出现）：输出并标记
    - 若已标记（重复出现）：跳过
- 时间复杂度：O(n) 每个元素处理一次
- 空间复杂度：O(k) k为不同元素数量

顺序保留特性：

PLAINTEXT

输入: [3, 1, 2, 1, 3]
处理流程:
  读取3 → 未出现 → 输出3 → 标记3
  读取1 → 未出现 → 输出1 → 标记1
  读取2 → 未出现 → 输出2 → 标记2
  读取1 → 已标记 → 跳过
  读取3 → 已标记 → 跳过
输出结果: 3 1 2

关键优势：

顺序保留：保持元素首次出现的原始顺序
高效去重：哈希表提供 O(1) 的平均查找/插入时间
内存优化：仅需存储不重复元素的状态信息
多组数据处理：s.clear() 确保测试用例间完全隔离

4.P1506 拯救oibh总部

题目分析

题目要求计算被围墙（*）完全包围的重要区域（0）的数量。洪水从外部涌入，只有被围墙完全围住的区域才能保护内部的0不被淹没。关键点在于识别与地图边界相连通的0区域（这些区域会被洪水淹没），剩下的0就是安全的。

解题思路

问题转化：所有与边界连通的0都会被洪水淹没，只有被围墙完全隔离的内部0才是安全的。
算法选择：使用广度优先搜索（BFS） 从地图边界开始遍历所有可达的0，并标记为已访问（表示会被淹没）。未被标记的0即为安全区域。
边界处理：地图的四条边界（第一行、最后一行、第一列、最后一列）是洪水入口，需特别处理。

代码实现

CPP

#include <iostream>
#include <vector>
#include <queue>
#include <cctype>
using namespace std;

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

int main() {
    int x, y;
    cin >> x >> y; // 读取地图行数x和列数y

    // 存储地图，每行一个字符串
    vector<string> grid(x);
    for (int i = 0; i < x; i++) {
        cin >> grid[i];
    }

    // 标记数组，记录每个位置是否被访问过（是否会被洪水淹没）
    vector<vector<bool>> visited(x, vector<bool>(y, false));

    // BFS队列，存储待访问的位置坐标
    queue<pair<int, int>> q;

    // 检查地图的四条边界，将边界上的'0'作为BFS起点
    // 第一行和最后一行
    for (int j = 0; j < y; j++) {
        if (grid[0][j] == '0' && !visited[0][j]) {
            visited[0][j] = true;
            q.push({0, j});
        }
        if (grid[x-1][j] == '0' && !visited[x-1][j]) {
            visited[x-1][j] = true;
            q.push({x-1, j});
        }
    }
    // 第一列和最后一列（跳过四个角避免重复）
    for (int i = 1; i < x-1; i++) {
        if (grid[i][0] == '0' && !visited[i][0]) {
            visited[i][0] = true;
            q.push({i, 0});
        }
        if (grid[i][y-1] == '0' && !visited[i][y-1]) {
            visited[i][y-1] = true;
            q.push({i, y-1});
        }
    }

    // BFS遍历：从边界开始标记所有可达的'0'
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x0 = cur.first, y0 = cur.second;

        // 遍历四个方向
        for (int k = 0; k < 4; k++) {
            int nx = x0 + dx[k], ny = y0 + dy[k];
            // 检查新位置是否在地图范围内
            if (nx >= 0 && nx < x && ny >= 0 && ny < y) {
                // 如果是'0'且未访问，则标记并入队
                if (grid[nx][ny] == '0' && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }

    // 统计未被淹没的'0'（未被标记的'0'）
    int count = 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (grid[i][j] == '0' && !visited[i][j]) {
                count++;
            }
        }
    }

    cout << count << endl; // 输出结果
    return 0;
}

代码详细注释

方向数组：dx和dy定义上、下、左、右四个移动方向，便于BFS遍历邻居。
地图读取：使用vector<string>存储地图，便于按行访问。
边界处理：
- 遍历第一行和最后一行，将边界上的0加入BFS队列。
- 遍历第一列和最后一列（跳过四个角避免重复），将边界上的0加入队列。
BFS遍历：
- 从队列中取出位置，检查四个方向的邻居。
- 如果邻居是0且未访问，标记为已访问并加入队列。
- 遇到围墙*或已访问位置则跳过。
安全区域统计：遍历整个地图，统计未被标记的0的数量。

算法原理

洪水填充思想：洪水从边界涌入，通过BFS模拟洪水蔓延过程，标记所有可达的0（这些区域会被淹没）。
围墙隔离：BFS遇到围墙*会停止，因此围墙内部的0不会被标记，代表安全区域。
时间复杂度：O(x×y)，每个位置至多访问一次。
空间复杂度：O(x×y)，用于存储地图和访问标记。

此算法高效地识别出安全区域，确保正确统计被围墙保护的0的数量。

5.P1141 01迷宫

为了解决这个问题，我们需要计算在给定的01迷宫中，从每个查询点出发能够到达的格子数量（包括自身）。移动规则是：在0上只能移动到相邻的1，在1上只能移动到相邻的0。

解题原理

问题分析：迷宫由0和1组成，移动规则要求相邻格子的值必须交替（0→1→0→1...）。因此，所有满足交替移动条件的格子形成一个个连通块。
连通块处理：使用BFS遍历整个迷宫，将每个连通块标记为唯一的ID，并记录每个连通块的大小（即包含的格子数）。
查询处理：对于每个查询，直接获取该点所属的连通块ID，并输出对应的连通块大小。
优化：预处理所有连通块，使得每次查询的时间复杂度为O(1)，整体时间复杂度为O(n² + m)。

完整代码

CPP

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    // visited 数组记录每个位置所属的连通块ID，初始为-1（未访问）
    vector<vector<int>> visited(n, vector<int>(n, -1));
    // componentSizes 存储每个连通块的大小
    vector<int> componentSizes;
    // 方向数组：上、下、左、右
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int currentID = 0; // 当前连通块的ID

    // 遍历网格中的每个格子
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 如果当前格子未被访问，则开始BFS
            if (visited[i][j] == -1) {
                int size = 0; // 当前连通块的大小
                queue<pair<int, int>> q;
                q.push({i, j});
                visited[i][j] = currentID; // 标记当前格子
                size++; // 连通块大小加1

                // BFS遍历连通块
                while (!q.empty()) {
                    auto [r, c] = q.front();
                    q.pop();
                    char currentChar = grid[r][c]; // 当前格子的字符

                    // 遍历四个方向
                    for (const auto& dir : dirs) {
                        int nr = r + dir[0];
                        int nc = c + dir[1];
                        // 检查新位置是否在网格内
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                            // 检查是否满足移动规则（当前为0则相邻必须为1，反之亦然）
                            if ((currentChar == '0' && grid[nr][nc] == '1') ||
                                (currentChar == '1' && grid[nr][nc] == '0')) {
                                // 如果新位置未被访问
                                if (visited[nr][nc] == -1) {
                                    visited[nr][nc] = currentID; // 标记为当前连通块
                                    size++; // 更新连通块大小
                                    q.push({nr, nc}); // 加入队列
                                }
                            }
                        }
                    }
                }
                // 存储当前连通块的大小并更新ID
                componentSizes.push_back(size);
                currentID++;
            }
        }
    }

    // 处理每个查询
    for (int k = 0; k < m; k++) {
        int i, j;
        cin >> i >> j;
        // 转换为0-based索引
        i--; j--;
        // 获取该位置所属连通块的大小并输出
        cout << componentSizes[visited[i][j]] << '\n';
    }

    return 0;
}

代码解释

输入处理：
- 读取网格大小n和查询数量m。
- 读取n行字符串，存储迷宫网格。
连通块标记：
- visited数组记录每个格子的连通块ID（初始为-1）。
- componentSizes向量存储每个连通块的大小。
- 使用方向数组dirs表示上、下、左、右四个移动方向。
BFS遍历：
- 遍历每个格子，若未被访问，则启动BFS。
- BFS过程中，检查相邻格子是否满足移动规则（0→1或1→0）。
- 标记连通块ID并统计连通块大小，存入componentSizes。
查询处理：
- 对每个查询，转换坐标（1-based转0-based）。
- 通过visited数组获取连通块ID，从componentSizes中读取大小并输出。

6.P1160 队列安排

复杂度分析

时间复杂度：O(n² + m)。预处理连通块需遍历整个网格（O(n²)），每次查询O(1)。
空间复杂度：O(n²)。存储visited数组和网格。

此方案高效处理了大规模网格和多次查询，确保在时间和空间上均满足要求。

CPP

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100005; // 最大学生数量

// 链表节点结构体
struct Node {
    Node* prev; // 前驱节点指针
    Node* next; // 后继节点指针
    int id;     // 学生编号

    Node() : prev(nullptr), next(nullptr), id(0) {}
};

Node nodes[MAXN];    // 节点数组，索引即学生编号
bool deleted[MAXN];  // 标记节点是否被删除
int head = -1;       // 链表头节点编号

int main() {
    int n;
    cin >> n;

    // 初始化第一个节点（1号学生）
    nodes[1].id = 1;
    head = 1; // 头节点设置为1

    // 处理2~n号学生的插入
    for (int i = 2; i <= n; i++) {
        int k, p;
        cin >> k >> p; // k是基准学生，p表示左右（0左1右）
        nodes[i].id = i; // 设置当前学生编号

        if (p == 1) { // 插入到k的右侧
            nodes[i].prev = &nodes[k];         // 当前节点的前驱是k
            nodes[i].next = nodes[k].next;     // 当前节点的后继是k的后继
            if (nodes[k].next) {
                nodes[k].next->prev = &nodes[i]; // 如果k有后继，更新其后继的前驱
            }
            nodes[k].next = &nodes[i];         // k的后继更新为当前节点
        } else { // 插入到k的左侧
            nodes[i].prev = nodes[k].prev;     // 当前节点的前驱是k的前驱
            nodes[i].next = &nodes[k];         // 当前节点的后继是k
            if (nodes[k].prev) {
                nodes[k].prev->next = &nodes[i]; // 如果k有前驱，更新其前驱的后继
            } else {
                head = i; // k无前驱说明k是头节点，更新头节点为当前节点
            }
            nodes[k].prev = &nodes[i];         // k的前驱更新为当前节点
        }
    }

    int M;
    cin >> M; // 读取删除操作数量
    memset(deleted, false, sizeof(deleted)); // 初始化删除标记数组

    // 处理M次删除操作
    for (int i = 0; i < M; i++) {
        int x;
        cin >> x; // 待删除学生编号
        if (deleted[x]) continue; // 已删除则忽略
        deleted[x] = true;        // 标记删除

        // 如果删除的是头节点，需要更新头节点
        if (head == x) {
            head = (nodes[x].next) ? nodes[x].next->id : -1;
        }

        // 调整链表指针，跳过被删除节点
        if (nodes[x].prev) {
            nodes[x].prev->next = nodes[x].next;
        }
        if (nodes[x].next) {
            nodes[x].next->prev = nodes[x].prev;
        }

        // 可选：断开被删除节点的指针
        nodes[x].prev = nullptr;
        nodes[x].next = nullptr;
    }

    // 输出结果
    if (head == -1) {
        cout << endl; // 链表为空
    } else {
        Node* cur = &nodes[head]; // 从头节点开始遍历
        while (cur) {
            cout << cur->id;      // 输出当前节点编号
            cur = cur->next;      // 移动到下一个节点
            if (cur) cout << " "; // 非最后一个节点输出空格
        }
        cout << endl;
    }

    return 0;
}

原理解释：

问题分析：
- 需要模拟一个动态链表，支持在任意节点左侧/右侧插入新节点，以及删除任意节点。
- 最后按从左到右顺序输出链表中的学生编号。
数据结构选择：
- 使用 双向链表 实现，因为插入和删除操作需要高效调整相邻节点关系。
- 用结构体数组 nodes 存储所有节点，数组下标对应学生编号，便于快速访问。
- 维护一个 head 变量记录链表最左侧节点（头节点）。
核心操作：
- 插入操作：
  - 右侧插入：新节点插入到 k 节点右侧，调整 k、k->next 和新节点的指针。
  - 左侧插入：新节点插入到 k 节点左侧，如果 k 是头节点，则更新头节点为新节点。
- 删除操作：
  - 标记节点为已删除，避免重复操作。
  - 调整相邻节点的指针，跳过被删除节点。
  - 如果删除的是头节点，将头节点更新为原头节点的后继（若存在）。
输出处理：
- 从头节点开始，沿 next 指针遍历链表，输出未被删除节点的编号。

关键点说明：

头节点维护：在左侧插入头节点或删除头节点时动态更新 head。
高效访问：通过数组下标直接访问节点，时间复杂度 O(1)。
空间优化：预分配节点数组，避免动态内存分配开销。
边界处理：处理链表为空、删除不存在的节点等特殊情况。

2025/7/24学校集训内容

文章操作

1.P8744 左孩子右兄弟

代码注释与原理说明

算法原理

问题目标

核心思想

计算过程

示例分析

时间复杂度

2.P1030 求先序排列

代码注释与原理说明

算法原理

问题目标

核心思想

关键步骤

递归终止条件

示例分析

时间复杂度

优化版本

3.P4305 不重复数字

代码原理详解：

关键优势：

4.P1506 拯救oibh总部

题目分析

解题思路

代码实现

代码详细注释

算法原理

5.P1141 01迷宫

解题原理

完整代码

代码解释

6.P1160 队列安排

复杂度分析

原理解释：

关键点说明：

相关推荐

评论

2025/7/24学校集训内容