2023南京理工大学计算机复试上机真题
2023南京理工大学计算机复试机试真题
历年南京理工大学计算机复试上机真题
在线评测：传送门：pgcode.cn
括号匹配二
题目描述
苗苗今天刚刚学会使用括号，不过他分不清小括号，中括号，大括号和尖括号，不知道怎么使用这些括号，请帮助他判断括号使用是否正确。
输入格式
输入只包含’<’，’(’，’{’，’[’，’>’，’)’，’}’，’]'的字符串（长度不超过 10000）
输出格式
对应每行输入，如果输入的字符串中的括号正确匹配则输出 yes，否则输出 no。
输入样例
(){}
输出样例
yes
求阶乘
题目描述
给出一个数 n(1<=n<=13)，求出它的阶乘。
输入格式
输入只有一个整数 n。
输出格式
对于输入的 n，求出它的阶乘并输出。
输入样例
3
输出样例
6
树的高度
题目描述
树是一种特殊的图结构，有根树是一个有固定根的树。
现在给定一棵有根树，编程求出树中所有节点到指定的根节点最远距离。
输入格式
第一行是两个整数 N，M（1<=N<=10000,1<=M<=N），表示数的顶点数和根节点的编号。
接下来 N-1 行，每行两个整数 u,v（1<=u,v<=N），表示编号为 u 的节点和编号为 v 的节点间有一条边。
输出格式
输出距离根节点最远的点到根的距离。
输入样例
5 5
1 2
1 4
1 5
2 3
输出样例
3
搬箱子
题目描述
华华要给厂里进一批新箱子共 n 个(n<=500)，编号为 1 到 n，用一个正整数 ai(1<=ai<=10000)(1<=i<=n)来表示编号为 i 的箱子的高度。
现在华华要按照编号从小到大的顺序选出 m 个箱子运到厂房，要确保编号大的箱子比编号小的箱子高。
也就是对于任意的 i<j 有 ai<aj，那么 m 最大可以是多少呢？
输入格式
第一行是正整数 n，表示 n 个箱子。
第二行 a1,a2…an 分别表示编号为 i 的箱子的高度。
输出格式
输出华华最多可以搬运的箱子个数。
输入样例
7
1 7 3 5 9 4 8
输出样例
4
女士优先
题目描述
午餐时间还未到，饥饿的程序员们早早就在食堂门口排队了。
假设现在的队列是这样的：MFM。
从左往右，第一位是男程序员（Male），第二位是女程序员（Female）,第三位是一位男程序员。
但是男程序员不会让女程序员排在他们后面。
于是就会发生这样的情况：只要一位男程序员发现自己后面是一位女程序员，他就会和这位女程序员交换位置，这样的交换需要消耗一秒。
当然，在同一秒内可能会有多位男程序员和自己后面的女程序员交换位置。
现在，请问最少要消耗多长时间，队伍不再变动。
输入格式
输入一个字符串，仅包含‘M’和‘F’两种字母，表示当前的排队情况。
（最左边表示队伍头，字符串长度<=100000）
输出格式
队伍不再变动的时间。
输入样例
MMFF
输出样例
3
架线方案
题目描述
电信公司要在多个城市之间架设通信线路，有些城市之间可以架设，而有些由于条件限制不可以架设，可以架设线路的城市之间的架设线路成本为 c。
现有 n 个城市，求出使这 n 个城市互相联通最节省的费用。
输入格式
第一行是两个整数 n，m(2<=n<=100,1<=m<=n*(n-1)/2)。
n 表示城市数，m 表示可以架设的线路数。
接下来 m 行每行三个整数 a，b，c，表示编号为 a 的城市与编号为 b 的城市之间架设通信线路的成本为 c。
输出格式
对于每组测试数据，给出一个整数，表示最节省的费用。
(若不存在则输出-1)
输入样例
3 3
0 1 1
2 1 2
2 0 1
输出样例
2
最大递增子序列和
题目描述
一个数的序列 bi，当 b1 < b2 < … < bS 的时候，我们称这个序列是上升的。
对于给定的一个序列(a1, a2, …,aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里 1 <= i1 < i2 < … < iK <= N。
比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。
这些子序列中序列和最大为 18，为子序列(1, 3, 5, 9)的和。
你的任务，就是对于给定的序列，求出最大上升子序列和。
注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为 100，而最长上升子序列为(1, 2, 3)。
输入格式
输入包含多组测试数据。
每组测试数据由两行组成。
第一行是序列的长度 N (1 <= N <= 1000)。
第二行给出序列中的 N 个整数，这些整数的取值范围都在 0 到 10000（可能重复）。
输出格式
对于每组测试数据，输出其最大上升子序列和。
输入样例
7
1 7 3 5 9 4 8
输出样例
18
南京理工-最短路径问题
题目描述
给你 n 个点，m 条无向边，每条边都有长度 d 和花费 p，给你起点 s 终点 t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
输入格式
输入 n,m，点的编号是 1~n,然后是 m 行，每行 4 个数 a,b,d,p，表示 a 和 b 之间有一条边，且其长度为 d，花费为 p。
最后一行是两个数 s,t;起点 s，终点 t。
n 和 m 为 0 时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出格式
输出一行有两个数， 最短距离及其花费。
输入样例
3 2
1 2 5 6
2 3 4 5
1 3
0 0
输出样例
9 11
有趣的天平
题目描述
Gigel 有一种奇怪的“天平”，他想平衡它。
事实上，这种装置不同于任何其他普通的天平。
它订购了两条重量可忽略不计的手臂，每条手臂的长度为 15。
一些钩子连接在这些手臂上，Gigel 想挂上他收集的 G（1<=G<=20）个砝码，因为他知道这些砝码重量在 1…25.范围内有不同的值。
钩子可以放下任何重量的砝码（一个钩子下可以放多个砝码），但他必须使用完所有的重量。
最后，Gigel 利用他在国家信息学奥林匹克运动会上获得的经验，成功地平衡了设备。
现在，他想知道该设备可以通过多少种方式实现平衡。
知道钩子的位置和砝码重量后，编写一个程序来计算平衡设备的可能性。
输入格式
第一行包含数字 C（2<=C<=20）和数字 G（2<=G<=20）
下一行包含范围为-15.15 的 C 个整数（这些数字也不同，按升序排序），表示钩子的位置；
每个数字表示相对于 X 轴上的天平中心的位置（当没有连接重物时，设备平衡并与 X 轴对齐；距离的绝对值表示挂钩和平衡中心之间的距离，数字的符号决定挂钩所连接的平衡臂：左臂为“-”，右臂为“+”）；
在下一行，有 G 个自然数、不同的、按升序排列的数字，范围为 1…25，代表权重值。
输出格式
输出使天平平衡总共有多少种方案。
输入样例
2 3
-2 4
1 3 8
输出样例
1
堆排序问题
题目描述
给一个序列，要求把它调整为大顶堆需要交换的最小次数。
输入格式
第一行输入一个数 n，表示序列有 n 个整数
第二行输入 n 个整数
输出格式
输出结果
输入样例
3
1 2 3
输出样例
1
紧急支援
题目描述
紧急支援，你有一个直升机，可以飞过连续 k 个城市(可以飞 k 个城市中的任意一个)，但只能飞一次且所需时间固定 2h，给出相邻城市之间步行需要的时间 a(1)~a(n-1)。
现在要求出从城市 1 走到城市 n(即线性 1~n)最少时间。
输入格式
第一行输入 n 和 k 以及 h，表示有 n 个城市和可以连续飞 k 个城市，0<=k<=n-1。
第二行输入 n-1 个数，表示从起点开始相邻城市步行需要的时间
输出格式
如题
输入样例
5 2 1
3 6 2 4
输出样例
6
AQIP 操作
题目描述
给定一个字符串以及几个操作。
- A 操作后面跟一个字符 b 表示在字符串后面插入这个字符。
- I 操作后面跟两个字符 b，c 表示在字符串的第 b 个位置插入字符 c。
- Q 操作后面跟一个字符 b 表示查询字符串中字符 b 的数量并输出。
- P 操作表示输出整个字符串，每个字符中间用空格隔开
输入格式
第一行输入一行字符串
第二行输入一个整数 m，表示有 m 次操作
接下来 m 行输入操作指令
输出格式
如题
输入样例
abcde
4
A x
I 3 a
Q a
P
输出样例
2
abacdex