历年中南大学计算机考研复试机试真题
本文整理中南大学计算机考研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
最大连续子序列
题目描述
给定 ${K}$ 个整数的序列 ${ { N_1, N_2, ..., N_K } }$，其任意连续子序列可表示为 ${ { N_i, N_{i+1}, ..., N_j } }$，其中 ${1 \le i \le j \le K}$。
最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 ${ { -2, 11, -4, 13, -5, -2 } }$，其最大连续子序列为 ${ { 11, -4, 13 } }$，最大和为 20。
编写程序得到其中最大子序列的和并输出该子序列的第一个和最后一个元素的下标。
输入格式
测试输入包含若干测试用例，每个测试用例占 2 行，第 1 行给出正整数 ${K}$（${<100000}$），第 2 行给出 ${K}$ 个整数，每个整数的范围 -10000 至 10000，中间用空格分隔。
输出格式
对每个测试用例，在 1 行里输出最大和、最大连续子序列的第一个和最后一个元素的下标，中间用空格分隔。
如果最大连续子序列不唯一，则输出序号 ${i}$ 和 ${j}$ 最小的那个（如输入样例的第 2、3 组）。
若所有 ${K}$ 个元素都是负数，则定义其最大和为 0，输出 "0 0 0"。
数据范围
${K < 100000}$，每个整数的范围 ${-10000 \le N_i \le 10000}$
输入样例
8
6 -2 11 -4 13 -5 -2 10
20
-10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3
8
-1 -5 -2 3 -1 0 -2 0
4
-1 -2 -4 -3
输出样例
27 0 7
27 10 19
3 3 3
0 0 0
好坑的电子地图
题目描述
小明是今年参加复试的外校考生，他要去民主楼小礼堂签到。
由于对中南大学校本部很不熟悉，小明找到了这边读书的好朋友鲁大师，不巧，鲁大师在忙着自由探索项目的结题工作，不能给他带路，只好给他发了一份半成品的电子地图。
地图上只列出了校本部内的 ${N}$ 个点，${M}$ 条路，小明处于 ${S}$ 点，民主楼小礼堂是 ${T}$ 点。
小明感谢鲁大师，当然只是在拿到地图的一瞬间，后面的情况让他知道这半成品到底有多坑。
鲁大师制作的电子地图是带有语音提示功能的，但是在编号为奇数的点他要等 1 分钟才能告诉他具体怎么走，而在编号为偶数的点要等 2 分钟。
现在告诉你地图的具体情况，小明想知道他能不能在 ${A}$ 分钟内赶到民主楼小礼堂。
输入格式
输入数据有多组，每组占 ${M+1}$ 行，第一行有 5 个数字 ${N，M，S，T，A}$，接下来 ${M}$ 行，每行三个数字 ${u,v,t}$，代表每条路的两个顶点和步行时间。
（输入数据保证不含重边 ${0 < N < M < 1000}$）。
输出格式
对于每组输入数据，输出一行，小明能在 ${A}$ 分钟内赶到民主楼小礼堂输出 "YES" 和最少花费的时间，否则输出 "KENG"。
数据范围
${0 < N < M < 1000}$
输入样例
4 3 1 4 10
1 2 1
3 2 2
3 4 3
5 4 2 4 7
1 2 5
5 4 2
3 5 1
2 3 1
输出样例
YES 10
KENG
惠民工程
题目描述
市政府“惠民工程”的目标是在全市 ${n}$ 个居民点间之架设煤气管道（但不一定有直接的管道相连，只要能间接通过管道可达即可）。
很显然最多可架设 ${n(n-1)/2}$ 条管道，然而实际上要连通 ${n}$ 个居民点只需架设 ${n-1}$ 条管道就可以了。
现请你编写程序，计算出该惠民工程需要的最低成本。
输入格式
测试输入包含若干测试用例。
每个测试用例的第 1 行给出居民点数目 ${M}$（${\le 100}$）、评估的管道条数 ${N}$；随后的 ${N}$ 行对应居民点间管道的成本，每行给出一对正整数，分别是两个居民点的编号，以及此两居民点间管道的成本（也是正整数）。
为简单起见，居民点从 1 到 ${M}$ 编号。
输出格式
对每个测试用例，在 1 行里输出全市管道畅通所需要的最低成本。
若统计数据不足以保证畅通，则输出 “?”。
数据范围
${M \le 100}$
输入样例
3 3
1 2 1
1 3 2
2 3 4
3 1
2 3 2
输出样例
3
?
加油站
题目描述
一辆汽车加满油后可行驶 ${n}$ 公里。
旅途中有若干加油站。
设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
请对于给定的 ${n}$ 和 ${k}$ 个加油站位置，计算最少加油次数。
输入格式
输入包含多组测试用例。
对于每一组数据，其第 1 行有 2 个正整数 ${n}$（${1 \le n \le 5000}$）和 ${k}$（${1 \le k \le 5000}$）。
表示汽车加满油后可行驶 ${n}$ 公里，且旅途中有 ${k}$ 个加油站。
接下来的 1 行中，有 ${k+1}$ 个整数，表示第 ${k}$ 个加油站与第 ${k-1}$ 个加油站之间的距离。
第 0 个加油站表示出发地，汽车已加满油。
第 ${k+1}$ 个加油站表示目的地。
输出格式
数据输出一行。
如果所对应的输入数据数据可以到达，将计算的最少加油次数输出。
如果无法到达目的地，则输出 "NoSolution"。
数据范围
${1 \le n \le 5000}$，${1 \le k \le 5000}$
输入样例
7 7
1 2 3 4 5 1 6 6
输出样例
4
淘金
题目描述
在一片 ${n \times m}$ 的土地上，每一块 ${1 \times 1}$ 的区域里都有一定数量的金子。
这一天，你到这里来淘金，然而当地人告诉你，如果你挖了某一区域的金子，上一行，下一行，左边，右边的金子你都不能被允许挖了。
那么问题来了：你最多能淘金多少？
输入格式
多组数据输入。
对于每组数据，第一行两个数 ${n, m}$，表示土地的长和宽（${1 \le n,m \le 200}$），接下来 ${n}$ 行，每行 ${m}$ 个数，表示每个区域的金子数量，每个区域的金子数量不超过 1000。
输出格式
对于每组数据，输出最多得到的金子数量。
数据范围
${1 \le n,m \le 200}$，金子数量不超过 1000。
输入样例
4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6
输出样例
242