程序员基德

09-09 11:43 中国科学技术大学 C++ 发布于浙江

关注

【秋招笔试】2025.09.06科大讯飞秋招笔试改编题

✅ 秋招备战指南 ✅

💡 学习建议：

先尝试独立解题
对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

科大讯飞-0906

题目一：储水池管理系统

1️⃣：使用并查集维护连通的储水池区域

2️⃣：对每个区域维护总水量和储水池数量

3️⃣：利用连通器原理实现水量平衡计算

难度：中等

这道题目的关键在于理解连通器的物理原理，并将其转化为数据结构问题。通过并查集维护连通关系，配合总水量统计，可以高效处理动态的注水、抽水和查询操作。算法的核心是利用连通器中水位平衡的特性，避免了复杂的水量分配计算。

题目二：通信网络扩展计划

1️⃣：使用BFS按层级构建树结构

2️⃣：统计每个层级的基站数量和扩展费用

3️⃣：贪心策略选择费用最低的扩展方案

难度：中等

这道题目需要理解树的层级结构和扩展操作对宽度的影响。核心思路是将扩展问题转化为层级优化问题，通过贪心算法在有限预算下最大化网络容量。关键技巧是对每层级的扩展费用排序，然后通过前缀和快速计算最优扩展方案。

题目三：慈善基金分配系统

1️⃣：按激活时间排序处理成员

2️⃣：使用优先队列维护已激活成员的资金状态

3️⃣：模拟捐赠过程，优先从资金少的成员扣除

难度：中等偏难

这道题目需要精确模拟动态的资金分配过程。难点在于理解捐赠规则和处理顺序，以及如何高效地从多个成员中按资金多少进行扣除。通过优先队列（最小堆）可以确保总是从资金最少的成员开始处理，实现了算法的正确性和相对高效的时间复杂度。

01. 储水池管理系统

问题描述

小基是一名城市水务管理员，负责管理城市中的 $n$ 个储水池。这些储水池编号为 $1$ 到 $n$ ，每个储水池都有一个区域编号 $id_i$ 。为了提高供水效率，同一区域内的储水池通过地下管道相互连通，形成一个统一的供水系统。根据水力学原理，连通的储水池之间会自动平衡水位，确保同一区域内所有储水池的水量始终相等。

小基需要处理三种操作：

注水：向编号为 $a$ 的储水池注入 $b$ 升水
抽水：从编号为 $a$ 的储水池抽取 $b$ 升水
查询：查询编号为 $a$ 的储水池当前的水量

由于地下管道的连通性，当对某个储水池进行注水或抽水操作时，整个区域的水量会重新分配，使得同一区域内每个储水池的水量保持相等。

输入格式

第一行包含两个正整数 $n, m$ （ $1 \leq n, m \leq 10^5$ ），分别表示储水池数量和操作数量。

第二行包含 $n$ 个正整数 $id_1, id_2, \ldots, id_n$ （ $1 \leq id_i \leq n$ ），表示每个储水池所属的区域编号。

接下来 $m$ 行，每行描述一个操作：

若操作类型为 $1$ ，则输入三个整数 $1\ a\ b$ （ $1 \leq a \leq n, 1 \leq b \leq 10^4$ ），表示向储水池 $a$ 注入 $b$ 升水
若操作类型为 $2$ ，则输入三个整数 $2\ a\ b$ （ $1 \leq a \leq n, 1 \leq b \leq 10^4$ ），表示从储水池 $a$ 抽取 $b$ 升水（保证该区域有足够的水可抽取）
若操作类型为 $3$ ，则输入两个整数 $3\ a$ （ $1 \leq a \leq n$ ），表示查询储水池 $a$ 的水量

保证至少有一次查询操作。

输出格式

对于每个查询操作，输出一个实数，表示对应储水池的水量。

当答案与标准答案的相对误差不超过 $10^{-5}$ 时，答案被认为是正确的。具体地，设你的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-5}$ 时，你的答案被接受。

样例输入

6 8
1 2 2 2 3 1
1 3 10
3 2
2 3 2
3 3
1 1 9
1 5 10
3 5
3 6

样例输出

2.500000
3.500000
1.500000

样例说明：

样例1：储水池1和3连通，储水池2和4连通，储水池5独立。按操作顺序执行后的水量分配结果
样例2：储水池1和6连通，储水池2、3、4连通，储水池5独立。按操作顺序执行后的水量分配结果

数据范围：

$1 \leq n, m \leq 10^5$
$1 \leq id_i \leq n$
$1 \leq a \leq n$
$1 \leq b \leq 10^4$

题解

这道题目的核心是理解连通储水池的水量分配机制。由于同一区域内的储水池通过管道连通，根据连通器原理，水会自动达到平衡状态，因此同一区域内所有储水池的水量始终相等。

核心思路：

我们可以将问题转化为对每个连通区域维护两个信息：

该区域的总水量
该区域内储水池的数量

这样，区域内每个储水池的水量就等于总水量除以储水池数量。

算法步骤：

建立连通关系：使用并查集（Union-Find）数据结构，将具有相同区域编号的储水池合并到同一个连通分量中。
维护区域信息：对每个连通分量的根节点，维护该分量的总水量和储水池数量。
处理操作：
- 注水操作：将水量加到对应区域的总水量上
- 抽水操作：将水量从对应区域的总水量中减去
- 查询操作：返回该储水池所在区域的平均水量

技术要点：

使用路径压缩优化的并查集，查找操作的时间复杂度接近常数
注意浮点数精度问题，使用long double类型保证精度
并查集的size数组记录每个连通分量的大小

时间复杂度： $O(m \cdot \alpha(n))$ ，其中 $\alpha$ 是阿克曼函数的反函数，在实际应用中可视为常数。

空间复杂度： $O(n)$

这种解法充分利用了连通器的物理特性，通过数学建模将复杂的水量分配问题转化为简单的并查集操作，是一个典型的数据结构应用题。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

class DSU:
    def __init__(self, n):
        self.fa = list(range(n + 1))  # 父节点数组
        self.sz = [1] * (n + 1)       # 连通分量大小
    
    def find(self, x):
        # 路径压缩查找根节点
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def unite(self, x, y):
        # 合并两个连通分量
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.sz[rx] < self.sz[ry]:
            rx, ry = ry, rx
        self.fa[ry] = rx
        self.sz[rx] += self.sz[ry]
    
    def size(self, x):
        # 获取连通分量大小
        return self.sz[self.find(x)]

n, m = map(int, input().split())
ids = list(map(int, input().split()))

# 初始化并查集
dsu = DSU(n)
first_occur = {}

# 合并相同区域的储水池
for i in range(n):
    zone_id = ids[i]
    if zone_id in first_occur:
        dsu.unite(i + 1, first_occur[zone_id])
    else:
        first_occur[zone_id] = i + 1

# 每个区域的总水量
total_water = [0.0] * (n + 1)

# 处理操作
for _ in range(m):
    op = list(map(int, input().split()))
    if op[0] == 1:  # 注水操作
        _, pool, water = op
        root = dsu.find(pool)
        total_water[root] += water
    elif op[0] == 2:  # 抽水操作
        _, pool, water = op
        root = dsu.find(pool)
        total_water[root] -= water
    else:  # 查询操作
        _, pool = op
        root = dsu.find(pool)
        avg_water = total_water[root] / dsu.size(pool)
        print(f"{avg_water:.6f}")

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

struct DSU {
    vector<int> fa, sz;
    
    DSU(int n) : fa(n + 1), sz(n + 1, 1) {
        // 初始化并查集
        iota(fa.begin(), fa.end(), 0);
    }
    
    int find(int x) {
        // 路径压缩查找根节点
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    
    void unite(int x, int y) {
        // 合并两个连通分量
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        fa[y] = x;
        sz[x] += sz[y];
    }
    
    int size(int x) {
        // 获取连通分量大小
        return sz[find(x)];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> zone_id(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> zone_id[i];
    }
    
    // 初始化并查集
    DSU dsu(n);
    unordered_map<int, int> first_pool;
    
    // 合并相同区域的储水池
    for (int i = 1; i <= n; i++) {
        int zid = zone_id[i];
        if (first_pool.count(zid)) {
            dsu.unite(i, first_pool[zid]);
        } else {
            first_pool[zid] = i;
        }
    }
    
    // 每个区域的总水量
    vector<long double> total_water(n + 1, 0.0);
    
    cout << fixed << setprecision(6);
    
    // 处理操作
    for (int i = 0; i < m; i++) {
        int op;
        cin >> op;
        
        if (op == 1) {  // 注水操作
            int pool, water;
            cin >> pool >> water;
            int root = dsu.find(pool);
            total_water[root] += water;
        } else if (op == 2) {  // 抽水操作
            int pool, water;
            cin >> pool >> water;
            int root = dsu.find(pool);
            total_water[root] -= water;
        } else {  // 查询操作
            int pool;
            cin >> pool;
            int root = dsu.find(pool);
            long double avg_water = total_water[root] / dsu.size(pool);
            cout << avg_water << "\n";
        }
    }
    
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static class DSU {
        private int[] fa, sz;
        
        public DSU(int n) {
            fa = new int[n + 1];
            sz = new int[n + 1];
            // 初始化并查集
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
                sz[i] = 1;
            }
        }
        
        public int find(int x) {
            // 路径压缩查找根节点
            return fa[x] == x ? x : (fa[x] = find(fa[x]));
        }
        
        public void unite(int x, int y) {
            // 合并两个连通分量
            x = find(x);
            y = find(y);
            if (x == y) return;
            if (sz[x] < sz[y]) {
                int temp = x;
                x = y;
                y = temp;
            }
            fa[y] = x;
            sz[x] += sz[y];
        }
        
        public int size(int x) {
            // 获取连通分量大小
            return sz[find(x)];
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        
        line = br.readLine().split(" ");
        int[] zoneId = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            zoneId[i] = Integer.parseInt(line[i - 1]);
        }
        
        // 初始化并查集
        DSU dsu = new DSU(n);
        Map<Integer, Integer> firstPool = new HashMap<>();
        
        // 合并相同区域的储水池
        for (int i = 1; i <= n; i++) {
            int zid = zoneId[i];
            if (firstPool.containsKey(zid)) {
                dsu.unite(i, firstPool.get(zid));
            } else {
                firstPool.put(zid, i);
            }
        }
        
        // 每个区域的总水量
        double[] totalWater = new double[n + 1];
        
        // 处理操作
        for (int i = 0; i < m; i++) {
            line = br.readLine().split(" ");
            int op = Integer.parseInt(line[0]);
            
            if (op == 1) {  // 注水操作
                int pool = Integer.parseInt(line[1]);
                int water = Integer.parseInt(line[2]);
                int root = dsu.find(pool);
                totalWater[root] += water;
            } else if (op == 2) {  // 抽水操作
                int pool = Integer.parseInt(line[1]);
                int water = Integer.parseInt(line[2]);
                int root = dsu.find(pool);
                totalWater[root] -= water;
            } else {  // 查询操作
                int pool = Integer.parseInt(line[1]);
                int root = dsu.find(pool);
                double avgWater = totalWater[root] / dsu.size(pool);
                out.printf("%.6f\n", avgWater);
            }
        }
        
        out.close();
        br.close();
    }
}

02. 通信网络扩展计划

问题描述

小兰是一家电信公司的网络规划师，负责设计和扩展城市的通信网络。目前公司已经建立了一个由 $n$ 个基站组成的通信网络，这些基站按照树形结构连接，其中基站 $1$ 是核心基站。

为了提高网络覆盖率，小兰计划在现有网络中增设新的基站。每个现有基站 $i$ 都可以扩展出一个新的子基站，但需要消耗 $cost_i$ 单位的建设资金。每个基站最多只能扩展一次，且新建的基站不能再进行扩展。

网络的服务能力主要取决于网络的"层级宽度"，即同一网络层级中基站数量的最大值。小兰希望在有限的资金 $budget$ 内，通过合理的扩展计划使网络的层级宽度最大化。

请帮助小兰计算在给定预算下能够达到的最大层级宽度。

输入格式

每个测试文件包含多组测试数据。第一行包含一个正整数 $T$ （ $1 \leq T \leq 10^4$ ），表示测试数据的组数。

对于每组测试数据：

第一行包含两个正整数 $n, budget$ （ $1 \leq n, budget \leq 10^5$ ），分别表示现有基站数量和可用预算。

第二行包含 $n$ 个正整数 $cost_1, cost_2, \ldots, cost_n$ （ $1 \leq cost_i \leq 10^5$ ），其中 $cost_i$ 表示基站 $i$ 扩展新基站所需的费用。

接下来 $n-1$ 行，每行包含两个正整数 $u_i, v_i$ （ $1 \leq u_i, v_i \leq n, u_i \neq v_i$ ），表示基站 $u_i$ 和基站 $v_i$ 之间有直连链路。保证所有基站构成一棵树。

保证所有测试数据的 $n$ 之和不超过 $10^5$ 。