有基础班_day04考试

zxcvbnm

2025-07-05 16:17:07

发布于：上海

11阅读

0回复

0点赞

题目
最近公共祖先（暴力版）
有向图的邻接矩阵存储（加强版）
有向图的出度
是否有边

最近公共祖先（暴力版）

题目大意

给定一个从下标为 1 开始的数组，按如下规则构建二叉树：

根节点为下标 1；
对于任意下标 $x$ $x$ ：
- 左儿子是 $2x$ ；
- 右儿子是 $2x+1$ 。

接下来 $q$ 次询问，每次给出两个下标，问对应节点在这棵树中的最近公共祖先（LCA，Lowest Common Ancestor）下标。

题意分析

我们不需要真正建立树，只需要利用节点的下标来推导其父节点即可。

由于是完全二叉树模型（数组建树）：
- 节点 $x$ 的父节点是 $\lfloor x / 2 \rfloor$
只要将两个节点不断“上跳”，直到相遇，就是它们的最近公共祖先。

解题思路

对于每次查询：

给定两个节点 id1、id2；
不断令较大的节点“上跳”到它的父节点（即除以 2），直到 id1 == id2；
此时就是最近公共祖先。

这相当于在一棵树上往上跳，最坏情况下跳 $\log n$ 层（因为高度约为 $\log_2 n$ ）。

时间复杂度分析

每次查询最多跳 $\log n$ 次；
总复杂度： $O(q \cdot \log n)$ ；
对于 $q \leq 10^5$ ， $n \leq 10^5$ 是可以接受的。

代码演示

#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp; // 数组值没用到，只需下标关系
    }

    while (q--) {
        int x, y;
        cin >> x >> y;
        // 暴力上跳法
        while (x != y) {
            if (x > y) x /= 2;
            else y /= 2;
        }
        cout << x << '\n';
    }

    return 0;
}

有向图的邻接矩阵存储（加强版）

题目大意

给定一个包含 $N$ 个顶点、 $M$ 条边的有向图，每条边给出起点、终点和权值。请用邻接矩阵的形式表示该图。

邻接矩阵定义为一个 $N \times N$ $N \times N$ 的二维数组 g[i][j]，其中：
- 如果存在一条从点 $i$ 指向点 $j$ 的有向边，值为对应的权值；
- 否则值为 0。

输入格式

第一行两个整数 $N, M$ ，表示顶点数和边数；
接下来 $M$ 行，每行三个整数 $u, v, k$ 表示从点 $u$ 到点 $v$ 有一条权值为 $k$ 的边。

输出格式

输出 $N$ 行，每行 $N$ 个整数，表示邻接矩阵。

解题思路

我们直接定义一个二维数组 g[N+1][N+1] 初始化为 0。

对于每一条边 $(u, v, k)$ ，直接赋值：g[u][v] = k；
最后输出邻接矩阵即可。

时间复杂度

空间复杂度： $O(N^2)$ ，用于存储邻接矩阵；
时间复杂度： $O(M + N^2)$ ，读取 $M$ 条边并输出 $N \times N$ 的矩阵。

对 $N \le 10^3$ ， $N^2 = 10^6$ ，可以轻松通过。

C++ 代码演示

#include <iostream>
using namespace std;

const int MAXN = 1010;
int g[MAXN][MAXN]; // 邻接矩阵

int main() {

    int n, m;
    cin >> n >> m;

    // 输入边并赋权
    for (int i = 0; i < m; i++) {
        int u, v, k;
        cin >> u >> v >> k;
        g[u][v] = k;
    }

    // 输出邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << g[i][j];
            if (j != n) cout << ' ';
        }
        cout << '\n';
    }

    return 0;
}

有向图的出度

题目大意

给定一个有向图，包含 $N$ 个顶点和 $M$ 条有向边。每条边从结点 $u$ 指向结点 $v$ 。

你需要输出从每个点出发的有向边的条数（即每个结点的出度）。

输入格式

第一行输入两个整数 $N$ 和 $M$ ；
接下来 $M$ 行，每行两个整数 $u$ 和 $v$ ，表示一条从 $u$ 到 $v$ 的边。

输出格式

输出一行 $N$ 个整数，第 $i$ 个表示结点 $i$ 的出度。

解题思路

我们只需要统计每个结点作为起点的边有多少条即可。

操作过程：

初始化一个数组 outDeg[N+1] 全部设为 0；
遍历每条边 $(u, v)$ ，令 outDeg[u]++；
最后输出 outDeg[1] ~ outDeg[N]。

时间复杂度

遍历每条边： $O(M)$ ；
输出每个点的出度： $O(N)$ ；
总时间复杂度： $O(N + M)$ ，可以通过所有数据。

代码实现

#include <iostream>
using namespace std;

const int MAXN = 1e5 + 10;
int outDeg[MAXN]; // 出度数组

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        outDeg[u]++; // u 指向了 v，u 出度 +1
    }

    // 输出每个点的出度
    for (int i = 1; i <= n; i++) {
        cout << outDeg[i];
        if (i != n) cout << ' ';
    }

    return 0;
}

是否有边

解题思路

我们用 vector<node> adj[N+1] 存储每个节点的出边信息。

每个 adj[u] 中存的是所有从 u 出发的边 (v, w)，表示存在一条从 u 到 v 权值为 w 的边。

查找方案

查找时遍历 adj[x]，找到是否有 to == y 的边，有则输出权值，否则输出 0。

代码演示

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

const int N = 100010;
struct node
{
    int to;
    int val;
};
vector<node> adj[N]; // adj[u] = { {v1, w1}, {v2, w2}, ... }

int main() {

    int n, m, q;
    cin >> n >> m >> q;

    // 读入边
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    // 查询
    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        int found = 0;
        for (int p = 0; p < adj[x].size(); p++) {
            if (adj[x][p].to == y) {
                cout << adj[x][p].val << ' ';
                found = 1;
                break;
            }
        }
        if (!found) cout << 0 << ' ';
    }

    return 0;
}