复旦大学2020年机试答案

复旦大学2020年机试答案

明天就要复试了，赶紧过来临时抱佛脚一下，希望之后自己能取得一个满意的成绩。冲冲冲！！！！

A.斗牛

思路

枚举出5个整数中的三个，若三个之和为10的倍数，则停止枚举，将标志位置1，进而输出点数，若不存在3个之和倍数为10，则输出-1

code

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {int arr[5];int n;cin >> n;while (n--) {int sum = 0;int flag = 0;for (int i = 0; i < 5; i++){cin >> arr[i];sum += arr[i];}for(int i=0;i<3;i++)for(int j=i+1;j<4;j++)for (int k = j + 1; k < 5; k++) {if ((arr[i] + arr[j] + arr[k]) % 10 == 0) {flag = 1;break;}}if (!flag) cout << -1 << endl;else cout << sum%10 << endl;}return 0;
}

B.打地鼠

思路

方法一

采用贪心的思想，设置一个val保存已经选取序列的最大值，遍历数组，若当前元素比val大d，则将该元素并入选取序列，并将当前值置为val，通过局部最优进而导致全局最优。

方法二

采用动态规划的方法，dp[i]表示前i个元素中最多满足条件元素的个数。dp[1]=1,dp[i]= 前j个元素中的最大值 j属于（1-i）

code

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {int n, d;cin >> n >> d;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}sort(a.begin(), a.end());int val=a[0];  // 保存所选序列中最后一个元素int count = 1;for (int i = 1; i < n; i++) {if (a[i] - val >= d) {count++;val = a[i];}}cout << count << endl;return 0;
}

C.排队打饭

思路

模拟：记录上一个学生吃完饭的时间，然后与当前学生时间（a[i]+b[i]）进行比较，若超过最大等待时间，则输出-1，若未超过最大等待时间，则取上一次结束时间与当前开始时间的最大值作为开始吃饭时间，最终计算结束时间。

code

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {int n;cin >> n;vector<int> a(n);vector<int> t(n);vector<int> b(n);for (int i = 0; i < n; i++) {cin >> a[i] >> t[i] >> b[i];}int end = a[0]; // 上一个同学结束时间for (int i = 0; i < n; i++) {if (a[i] + b[i] >= end) {  int start = max(end, a[i]);cout << start << " ";end = start + t[i];}else cout << -1 << " ";}return 0;
}

D.二叉搜索树

思路

变建树变保存插入节点的父节点的值，这里采用hash表存储对应节点的父节点。不断寻找插入的位置，使用pre指向当前遍历的父节点，使用p指向当前遍历的节点。

code

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};int main() {int n;cin >> n;vector<int> arr(n);for (int i = 0; i < n; i++) {cin >> arr[i];}if(n==0) return 0;TreeNode* root = new TreeNode(arr[0]);unordered_map<int, int> umap;umap[root->val] = 0;for (int i = 1; i < n; i++) {TreeNode* p = root;TreeNode* pre = nullptr;while (p) {if (p->val > arr[i]) {pre = p;p = p->left;}else if (p->val < arr[i]) {pre = p;p = p->right;}else return 0;}if (pre->val > arr[i]) {pre->left = new TreeNode(arr[i]);umap[arr[i]] = pre->val;}else {pre->right = new TreeNode(arr[i]);umap[arr[i]] = pre->val;}}sort(arr.begin(), d());for (int i = 0; i < n; i++) {cout << umap[arr[i]] << " ";}return 0;
}

E.序列

思路

采用动态规划，由于第i个位置的均方权重仅与前一位有关，所以遍历前一位分别为0-9与当前为取j的最小权重，另外需要对边界进行额外处理。
d p [ i ] [ j ] 表 示 第 i 个 位 置 为 j 的 最 小 权 重 ， j 属 于 0 − 9 dp[i][j]表示第i个位置为j的最小权重，j属于0-9 dp[i][j]表示第i个位置为j的最小权重，j属于0−9

code

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}// dp[i][j] 在第i个位置上为j的最小权重vector<vector<int>> dp(n, vector<int>(10, INF));// 处理边界for (int i = 0; i < 10; i++)dp[0][i] = abs(a[0] - i);for (int i = 1; i < n; i++)for (int j = 0; j < 10; j++)for (int k = 0; k < 10; k++) {dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(a[i] - j) + (j - k) * (j - k));}int min_val = INF;for (int i = 0; i < 10; i++) {min_val = min(dp[n - 1][i], min_val);}cout << min_val << endl;return 0;
}