2025年中国海洋大学计算机保研机试真题
本文整理中国海洋大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
学生排队
题目描述
体育老师小明要将自己班上的学生按顺序排队。
他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。
一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。
例如，下面给出了一组移动的例子，例子中学生的人数为 $8$ 人。
$0$) 初始队列中学生的学号依次为 $1, 2, 3, 4, 5, 6, 7, 8$;
$1$) 第一次调整，命令为“ $3$ 号同学向后移动 $2$ ”，表示 $3$ 号同学出队，向后移动 $2$ 名同学的距离，再插入到队列中，新队列中学生的学号依次为 $1, 2, 4, 5, 3, 6, 7, 8$;
$2$) 第二次调整，命令为“ $8$ 号同学向前移动 $3$ ”，表示 $8$ 号同学出队，向前移动 $3$ 名同学的距离，再插入到队列中，新队列中学生的学号依次为 $1, 2, 4, 5, 8, 3, 6, 7$;
$3$) 第三次调整，命令为“ $3$ 号同学向前移动 $2$ ”，表示 $3$ 号同学出队，向前移动 $2$ 名同学的距离，再插入到队列中，新队列中学生的学号依次为 $1, 2, 4, 3, 5, 8, 6, 7$。
小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？
请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。
在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。
在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
输入格式
输入的第一行包含一个整数 $n$ ，表示学生的数量，学生的学号由 $1$ 到 $n$ 编号。
第二行包含一个整数 $m$ ，表示调整的次数。
接下来 $m$ 行，每行两个整数 $p, q$ ，如果 $q$ 为正，表示学号为 $p$ 的同学向后移动 $q$ ，如果 $q$ 为负，表示学号为 $p$ 的同学向前移动 $-q$ 。
其中， $n, m \leq 100$ 。
输出格式
输出一行，包含 $n$ 个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。
输入样例
8
3
3 2
8 -3
3 -2
输出样例
1 2 4 3 5 8 6 7
学生排队
题目描述
体育老师小明要将自己班上的学生按顺序排队。
他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。
一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。
例如，下面给出了一组移动的例子，例子中学生的人数为 $8$ 人：
-
初始队列中学生的学号依次为 $1, 2, 3, 4, 5, 6, 7, 8$；
-
第一次调整，命令为“$3$ 号同学向后移动 $2$”，表示 $3$ 号同学出队，向后移动 $2$ 名同学的距离，再插入到队列中，新队列中学生的学号依次为 $1, 2, 4, 5, 3, 6, 7, 8$；
-
第二次调整，命令为“$8$ 号同学向前移动 $3$”，表示 $8$ 号同学出队，向前移动 $3$ 名同学的距离，再插入到队列中，新队列中学生的学号依次为 $1, 2, 4, 5, 8, 3, 6, 7$；
-
第三次调整，命令为“$3$ 号同学向前移动 $2$”，表示 $3$ 号同学出队，向前移动 $2$ 名同学的距离，再插入到队列中，新队列中学生的学号依次为 $1, 2, 4, 3, 5, 8, 6, 7$。
小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？
请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。
在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。
在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
输入格式
输入的第一行包含一个整数 $n$，表示学生的数量，学生的学号由 $1$ 到 $n$ 编号。
第二行包含一个整数 $m$，表示调整的次数。
接下来 $m$ 行，每行两个整数 $p, q$，如果 $q$ 为正，表示学号为 $p$ 的同学向后移动 $q$，如果 $q$ 为负，表示学号为 $p$ 的同学向前移动 $-q$。
输出格式
输出一行，包含 $n$ 个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。
输入样例
8
3
3 2
8 -3
3 -2
输出样例
1 2 4 3 5 8 6 7
交通规划
题目描述
$G$ 国国王来中国参观后，被中国的高速铁路深深的震撼，决定为自己的国家也建设一个高速铁路系统。
建设高速铁路投入非常大，为了节约建设成本，$G4 国国王决定不新建铁路，而是将已有的铁路改造成高速铁路。
现在，请你为 $G$ 国国王提供一个方案，将现有的一部分铁路改造成高速铁路，使得任何两个城市间都可以通过高速铁路到达，而且从所有城市乘坐高速铁路到首都的最短路程和原来一样长。
请你告诉 $G$ 国国王在这些条件下最少要改造多长的铁路。
输入格式
输入的第一行包含两个整数 $n$, $m$，分别表示G国城市的数量和城市间铁路的数量。
所有的城市由 $1$ 到 $n$ 编号，首都为 $1$ 号。
接下来 $m$ 行，每行三个整数 $a$, $b$, $c$，表示城市 $a$ 和城市 $b$ 之间有一条长度为 $c$ 的双向铁路。
这条铁路不会经过 $a$ 和 $b$ 以外的城市。
输出格式
输出一行，表示在满足条件的情况下最少要改造的铁路长度。
输入样例
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
输出样例
11