中南大学2025年第二批预推免机试题解

试题来源于中南大学2025年第二批预推免上机测试。咕咕很久了一直没有写下来，今天终于抽出时间记录一下。

一共 A-E 五道题，每个题目基本上都需要输入多组测试数据，有的题目没有在输入开头提供测试数据的个数，导致测试时有部分同学不会输入爆零。另外需要记得多测清空。

个人过题顺序：CBADE，感觉编排顺序不太好，A 题放了个臭模拟，其实 B 题才是最简单的。做题之前可以先概览一遍所有的题目，不用和第一题死磕（老师人挺好，测试中途有提醒考生）。

A题

题目大意

给定类似 1a2(3xy(ab)) 的字符串，根据数字重复其后的内容，需要正确处理括号（括号可能嵌套）。输入的字符串长度应该是不超过几百。

例如：

变换前	变换后
abc	abc
(a)	a
1a	a
2a3(b)	aabbb
2(1a2(b))	abbabb

题目思路

题目需要处理的字符串较短，主要需要把整个处理过程写对。可以编写一个递归程序来处理括号。

反正就是模拟，如果动手写过编译原理里面的 Lexer 程序应该这个题也能写出来。程序写多了模拟题就不难。

B题

题目大意

给定 $M$ 段内存，$N$ 个分配请求，每段内存和分配请求都有一个大小，一个请求只能被分配一段内存，且该段内存的，问能满足几个分配请求。

数据范围：$1\le M,N\le 200$

题目思路

先对内存段、分配请求按照大小排序，然后从小到大为分配请求寻找合适的内存段，也即当前未使用的内存段中最小且大小能够满足该请求的一段。输出分配成功的个数即可。

时间复杂度：$O(M\log{M} + N\log{N})$

C题

题目大意

给定一张 $N$ 个点, $M$ 条边的无向图，求联通块个数。

数据范围： $2 \le N \le 100,000; 1 \le M \le 100,000$

题目思路

可以使用 DFS/BFS 从每个未访问的点出发，将可达的点标记未已访问。最后进行搜索的次数就是连通块的个数。
也可以使用并查集，初始连通块个数设为 $N$，然后根据边做合并，当不同的连通块合并时，连通块个数减 1 即可（赛时采用，正好后面 D 题也要写并查集）

时间复杂度：$O(N+M)$

D题

题目大意

给定一张 $N$ 个点，$M$ 条边的带权无向图，其边分为两种类型，求一张生成图，使生成图中包含原图所有的顶点且连通，但其中一类边要求在生成图中至少有一条，最小化生成图的权值。

如果存在符合条件的生成树，输出该生成树的权值和；否则输出 $-1$

数据范围： $2 \le N \le 100,000; 1 \le M \le 100,000$ 并且 $\sum^{M}_{i=1}{c_i} \le 1e9$
$c_i$ 为第 $i$ 条边的权值。

题目思路

首先不考虑边的类型利用 $Kruskal$ 算法生成一颗最小生成树：

如果生成结果中含有该类边，那么答案就是该颗最小生成树的权值和
如果生成的结果中不含该类边，那么选取权值最小的一条该类边加入初始边集合，再求最小生成树，其权值和作为答案
也可能存在本来就没有该类边的情况，此时输出 $-1$

时间复杂度：$O(M\log{M})$

E题

题目大意

给定一个长度为 $N$ 的，只含 26 个小写字母的字符串 $S$。你可以在该字符串的任意位置插入字符，求使得这个字符串变成回文串的最小操作次数。

数据范围： $1\le N\le 5,000$

题目思路

考虑回文串的中心区间（一个或两个字符），原字符串被分割为 $AxB$ 或 $AxxB$ 的形式，我们的目标变为：将 $S_1=A$ 和 $S_2=B^R$ ($B$ 的翻转串) 两个字符串，通过在两个串中插入字符，使得两个字符串最终变为相同的串。

而在串 $S_1$ 中插入一个字符，其实就相当于在 $S_2$ 中删除一个字符，因此这个新问题的答案即是求 $S_1, S_2$ 的编辑距离。而 $S_1$ 是原串 $S$ 的前缀，$S_2$ 是原串的翻转 $S^R$ 的前缀，在求解 $S, S^R$ 的编辑距离中，这个子问题的答案已经保存在状态空间。

因此只需求 $S, S^R$ 的编辑距离，再根据中心查找 DP 状态空间，取其中的最小值即可。

时间复杂度 $O(N^2)$.