历年南京理工大学计算机保研机试真题
本文整理南京理工大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
架线方案
题目描述
电信公司要在多个城市之间架设通信线路，有些城市之间可以架设，而有些由于条件限制不可以架设。
可以架设线路的城市之间的架设线路成本为 $c$ 。
现有 $n$ 个城市，求出使这 $n$ 个城市互相联通最节省的费用。
输入格式
输入的第一行是一个正整数 $k$ $(1 \leq k \leq 100)$ ，表示有 $k$ 组测试数据。
每组测试数据第一行是两个整数 $n$ , $m$ $(2 \leq n \leq 100, 1 \leq m \leq \frac{n \times (n - 1)}{2})$ ，$n$ 表示城市数，$m$ 表示可以架设的线路数。
接下来 $m$ 行每行三个整数 $a$ , $b$ , $c$ ，表示编号为 $a$ 的城市与编号为 $b$ 的城市之间架设通信线路的成本为 $c$ 。
输出格式
对于每组测试数据，给出一个整数，表示最节省的费用。
（若不存在则输出 $-1$ ）
输入样例
1
3 3
0 1 1
1 2 2
0 2 3
输出样例
3
最长递增子序列
题目描述
华华要给厂里进一批新箱子共 $n$ 个 ($n \leq 500$)，编号为 $1$ 到 $n$，用一个正整数 $a_i$ ($1 \leq a_i \leq 10000$) ($1 \leq i \leq n$) 来表示编号为 $i$ 的箱子的高度。
现在华华要按照编号从小到大的顺序选出 $m$ 个箱子运到厂房，要确保编号大的箱子比编号小的箱子高。
也就是对于任意的 $i < j$ 有 $a_i < a_j$，那么 $m$ 最大可以是多少呢？
输入格式
第一行是正整数 $n$，表示 $n$ 个箱子，第二行 $a_1, a_2, \ldots, a_n$ 分别表示编号为 $i$ 的箱子的高度。
输出格式
输出华华最多可以搬运的箱子个数。
输入样例
7
1 7 3 5 9 4 8
输出样例
4
括号匹配
题目描述
苗苗今天刚刚学会使用括号，不过他分不清小括号，中括号，大括号和尖括号，不知道怎么使用这些括号，请帮助他判断括号使用是否正确。
输入格式
输入六行只包含 $<, (, [, {, >, ), ], }$ 的字符串（长度不超过 $10000$）。
输出格式
对应每行输入，如果输入的字符串中的括号正确匹配则输出 $yes$，否则输出 $no$。
输入样例
<<>>
[][]
{}{}
()()
<>
[]
输出样例
yes
yes
yes
yes
yes
yes
女士优先
题目描述
午餐时间还未到，饥饿的程序员们早早就在食堂门口排队了。
假设现在的队列是这样的：$MFM$。
从左往右，第一位是男程序员($Male$)，第二位是女程序员($Female$)，第三位是一位男程序员。
但是男程序员不会让女程序员排在他们后面，于是就会发生这样的情况：只要一位男程序员发现自己后面是一位女程序员，他就会和这位女程序员交换位置，这样的交换需要消耗一秒。
当然，在同一秒内可能会有多位男程序员和自己后面的女程序员交换位置。
现在，请问最少要消耗多长时间，队伍不再变动。
输入格式
输入一个字符串，仅包含 $'M'$ 和 $'F'$ 两种字母，表示当前的排队情况。
（最左边表示队伍头，字符串长度 $<= 100000$）
输出格式
输出队伍不再变动的时间。
输入样例
MMFF
输出样例
3