复旦大学2020年机试答案

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

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

#include 
#include 
#include 
#include 
#include 
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;
}

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

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

#include 
#include 
#include 
#include 
#include 
using namespace std;
int main() {
    int n, d;
    cin >> n >> d;
    vector 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;
}

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

#include 
#include 
#include 
#include 
#include 
using namespace std;
int main() {
    int n;
    cin >> n;
    vector a(n);
    vector t(n);
    vector 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;
}

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

#include 
#include 
#include 
#include 
#include 
#include 
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 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 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(), arr.end());
    for (int i = 0; i < n; i++) {
        cout << umap[arr[i]] << " ";
    }
    return 0;
}

采用动态规划，由于第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

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    int n;
    cin >> n;
    vector a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // dp[i][j] 在第i个位置上为j的最小权重
    vector> dp(n, vector(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;
}