2020复旦大学计算机考研机试题详解
写在前面
复旦巨喜欢考动规，建议好好准备
A、斗牛
假设我们有五位取值在0至9之间的数字a₁到a₅。当且仅当选出其中三位且这三者的总和为10的倍数（包括零）时，则此五位数字的权重即为此两位未被选取数字之总和对十取余所得的结果。值得注意的是，在满足上述条件的情形下（若有多个三元组可达成目标），剩余两位数字之总和对十取余的结果必然一致；反之若无法选出符合要求的三位，则此五位数字组合的权重赋值为-1。现提供T组测试数据集供评估计算使用
【输⼊格式】 第⼀⾏⼀个整数 T (1<=T<=1000)，表⽰数据组数。 接下来 T ⾏，每⾏ 5 个 0~9 的整数，表⽰⼀组数据。
【输出格式】输出 T ⾏，每⾏⼀个整数，表⽰每组数据中五个整数的权值。
【样例输⼊】
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8【样例输出】
2
-1
-1
0
解释
解释
答案解析
基本思路：
其实就是判断是否有三数之和为10的倍数，而且确定总共只有五个数，那么可以用fou循环来解决，但是为了代码美观而且看起来牛掰点，还是使用了回溯法，二者的时间复杂度和空间复杂度是相同的。最后如果三数之和为10的倍数，那么只要五数之和减去三数之和就可以了。
时间复杂度：O(n)
空间复杂度：O(1)
回溯法：通过visited数组来标记每个元素是否已被访问过，在每次循环中依次选择一个未被访问过的元素，并继续递归处理剩余的未被选中的元素。
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//回溯法得到其中三数之和，若没有10的倍数，返回-1
int judge(int sum,vector<int>& visited,vector<int>D,int num) {
if (num > 3) return -1;
if (num == 3 && sum % 10 == 0) return sum;
for (int i = 0; i < D.size(); i++) {
if (visited[i] == 0) {
visited[i] = 1;
int f = judge(sum + D[i], visited, D, num + 1);
if (f != -1) return f;
visited[i] = 0;
}
}
return -1;
}
int main()
{
int T;
cin >> T;
int N = 5;
vector<vector<int>>data(T, vector<int>(N));
for (int i = 0; i < T; i++) {
for (int j = 0; j < N; j++) {
cin >> data[i][j];
}
}
vector<int>result;
vector<int> visited(N, 0); //记录已被访问过的数
for (int i = 0; i < T; i++) {
int sum = 0, num = 0;
fill(visited.begin(), visited.end(), 0);
int flag = judge(sum, visited, data[i], num);
if (flag != -1) { //存在三数之和为10的倍数
int S = 0;
for (int j = 0; j < N; j++) S += data[i][j];
result.push_back((S - flag) % 10); //总和减去三数之和就是剩余两数之和
}
else result.push_back(flag);
}
for (int i = 0; i < result.size(); i++) cout << result[i] << endl;
}打地鼠
设有n个整数a₁, a₂, …, aₙ和一个d值，请确定在排序这些整数后满足任意两个相邻元素之差至少为d的情况下，最多能选出多少这样的数字。
输⼊格式
输出格式
【输出格式】 仅⼀⾏⼀个整数，表⽰答案。
【样例输⼊】
6 2
1 4 2 8 5 7【样例输出】
3
解释
解释
答案解析
基本思路：
有两种方法，一种是动规，一种是贪心。这里我使用的是贪心
首先递增排序，data[i]代表第 i 个数，d代表差，那么：
1、如果data[j]-data[i]>=d,由于数据增序排列，那么data[k] (j<k<n) 与data[i]的差也必定大于等于d,因此可将data[i]加入结果集；同时从i到j的任意两数之差必定小于d，因此从j开始重新寻找。
2、如果data[j]-data[i]<d,那就遍历 j+1
时间复杂度：O(nlogn)
空间复杂度：O(1)
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, d;
cin >> n >> d;
vector<int>data(n);
for (int i = 0; i < data.size(); i++) cin >> data[i];
sort(data.begin(), data.end()); //从小到大排序
int num = 0;
if (n < 2) { //只有一个整数
cout << num << endl;
return 0;
}
for (int i = 0, j = 1; j < data.size();) {
if (data[j] - data[i] >= d) {
num++;
i = j;
j++;
}
else j++;
}
if (num == 0) cout << num << endl; //没有符合条件的数
else cout << num + 1 << endl; //由于每次只将较小的数加入结果集，因此最后还需将最后的大数加入结果集
return 0;
}C、排队打饭
当下课铃响后,有n位同学依次到达学校食堂进行排队取餐.每位同学都有一个确定的到达时间和用餐所需时间,具体记为ai和ti.此外,每位同学还有一个等待时间上限bi,即如果他在ai+bi秒的时间段内仍未轮到他开始用餐,那么他将离开队列寻找其他就餐地点.问题要求计算出每位同学的具体用餐起始时间,或者判断其是否未能按时用餐（若未能按时则输出-1）.
输⼊格式
输入格式
输出格式
输出格式
输出要求
【样例输⼊】
4
1 3 3
2 2 2
3 9 1
4 3 2
【样例输出】
1 4 -1 6
解释
答案解析
主要思路
定义endtime变量用于记录上一位同学完成打饭的时间。那么当前同学的起始时间若不低于endtime，则无需等待即可开始服务；否则的话，则将被安排在endtime时刻开始服务，并计算其等待时间是否超过最长允许等待时间。
对于时间复杂度分析而言，在默认情况下各同学按照递增顺序到达食堂窗口进行打饭操作的情况下，只需对所有到达事件进行遍历即可完成计算；其复杂度属于O(n)级别。
空间复杂度仅为O(1), 仅需维护一个变量用于存储上一位同学的结束时刻。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<long long int>>data(n, vector<long long int>(3));
for (int i = 0; i < data.size(); i++){
for (int j = 0; j < data[i].size(); j++) {
cin >> data[i][j];
}
}
long long int endtime = 0; //记录上一个学生打饭结束的时间
vector<long long int>result;
for (int i = 0; i < data.size(); i++) {
if (data[i][0] >= endtime) { //第i位学生达到时无人打饭，可以直接开始打饭
result.push_back(data[i][0]);
endtime = data[i][0] + data[i][1];
}
else { //第i位学生正好有人打饭,那么第i位学生的等待时间=上一位学生的结束时间-第i位学生的开始时间
if (endtime - data[i][0] > data[i][2]) result.push_back(-1);
else {
result.push_back(endtime);
endtime = endtime + data[i][1];
}
}
}
for (int i = 0; i < result.size(); i++) cout << result[i] << ' ';
return 0;
}D、二叉搜索树
设P为长度为n的一个排列，并满足包含全部1到n不重复元素的情况。在空二叉搜索树中按顺序依次插入P中的每个元素（遵循左子树值小于父节点且右子树值大于父节点的原则），最终问题在于确定每个叶子结点在其生成过程中所附加的那个父结点的具体数值是多少？特别地，在这种情况下根结点被认为是无父结点存在的（其父数值视为0）。
输⼊格式
输入格式
输出格式
输出格式
输出格式
【样例输⼊】
5
2 3 5 1 4
【样例输出】
2 0 2 5 3
【样例解释】
最后建出来的⼆叉搜索树如下：
1 的⽗亲为 2，2 为根结点，所以⽗亲为 0，3 的⽗亲为 2，4 的⽗亲为 5，5 的⽗亲为 3。
答案解析
主要思路
这是最难的一题了，做是能做出来，但是基本都超时，这里介绍两种方法：
第一种方法：最简单直接的方法其实就是求解搜索二叉树的父节点问题。通过构建一棵搜索二叉树来实现这一目标确实非常有效。
时间复杂度为O(n^2)。
空间复杂度为O(n)。
代码
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef struct node {
int v;
node* left;
node* right;
}node;
int main()
{
//边建树边查找，n2
int n;
cin >> n;
vector<int>data(n + 1);
for (int i = 1; i < data.size(); i++) cin >> data[i];
vector<int>result(n + 1);
node* T = new node;
T->v = 0; T->left = NULL; T->right = NULL;
//边遍历边构造二叉搜索树，在找到插入位置时，同时保存父节点
for (int i = 1; i < data.size(); i++) {
node* p = T;
while (true) {
if (data[i] > p->v) {
if (p->right) p = p->right;
else {
node* q = new node;
q->v = data[i]; q->left = NULL; q->right = NULL;
p->right = q;
break;
}
}
else {
if (p->left) p = p->left;
else {
node* q = new node;
q->v = data[i]; q->left = NULL; q->right = NULL;
p->left = q;
break;
}
}
}
result[data[i]] = p->v;
}
for (int i = 1; i < result.size(); i++) cout << result[i] << ' ';
return 0;
}第二种：
使用f数组存储每个节点的父亲信息，并记录每个节点所在的层级（初始时根节点设为第0层）以及最大值mx：
- 若新加入的权值大于当前最大值mx，则其父必为mx，并更新mx并将该元素层级加入层级映射；
- 当新插入元素权值小于当前最大值时，则需通过二分查找法确定其前驱pre和后继next；
- 由于中序遍历结果必然呈现递增序列特性，则新元素的位置必然位于pre与next之间；
- 若预后继层高高于先驱层高，则应将新元素附加在预后继左侧；反之则附加于先驱右侧；
时间复杂度为O(nlogn)，空间复杂度为O(n)
代码
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int>father(n + 1);
map<int, int>dict;
dict[0] = 0;
int maxn = 0;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
if (t > maxn) {
father[t] = maxn;
dict[t] = dict[maxn] + 1;
maxn = t;
}
else {
map<int, int>::iterator small = dict.upper_bound(t);
map<int, int>::iterator big = small--;
if (big->second > small->second) {
father[t] = big->first;
dict[t] = big->second + 1;
}
else {
father[t] = small->first;
dict[t] = small->second + 1;
}
}
}
for (int i = 1; i < father.size(); i++) cout << father[i] << ' ';
}E、序列
给定一个长度为n的整数序列A（其中每个元素都在0到9之间），以及一个与A长度相同的整数序列B，在以下方面计算其总权重：第一部分是对所有i（1≤i≤n）的位置上A_i与B_i绝对差值之和；第二部分是对所有j（1≤j<n）的位置上相邻元素差值平方之和。现在的问题是在所有长度为n的整数序列中找到使得上述总权重最小的那个序列，并求出该最小总权重是多少。
【输⼊格式】 第⼀⾏⼀个整数 n (1<=n<=10^5)，表⽰序列 A 的⻓度。 第⼆⾏ n 个整数 a1, a2, …, an (0<=ai<=9, 1<=i<=n)，表⽰序列 A 中的元素。
【输出格式】仅⼀⾏⼀个整数，表⽰答案。
【样例输⼊】
6
1 4 2 8 5 7
【样例输出】
11
解释
主要思路
二维动态规划：dp[i][j]表示在处理至第i个元素时，在位置j处所取得的最小权值。其中，
for循环如下：
for (int i = 1; i < A.size(); i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(A[i]-j) + (abs(j-k)) * (abs(j-k)));
}
}
}
其中，
dp[i][j] = min(dp[i-1][k], ... ) 表示在B数组中第i位选择填入数值j的情况下与前一状态的所有可能情况k之间的最小权值。
初始化时将所有dp[0][*]设为INT_MAX。
计算过程中采用的是逐层递推的方式：
遍历B数组中前一位的所有可能数值k（从0到9），计算并比较这些情况下的总权值。
时间复杂度为O(n)，空间复杂度同样为O(n)
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <math.h>
using namespace std;
#define N 10
int main() {
int n;
cin >> n;
vector<int>A(n);
for (int i = 0; i < A.size(); i++) cin >> A[i];
vector<vector<int>>dp(n, vector<int>(N, INT_MAX));
for (int i = 0; i < N; i++) dp[0][i] = abs(i - A[0]);
for (int i = 1; i < A.size(); i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(A[i] - j) + (j - k)*(j - k));
}
}
}
int result = INT_MAX;
for (int i = 0; i < N; i++) result = min(result, dp[n - 1][i]);
cout << result;
return 0;
}