前言

有单选、多选题。占40分，三到编程题60分。

吐槽的是没给数据范围，也不能用自己的编译器。希望可以进面

第二题会的，分享一下思路，谢谢。

编程题

1 dfs

对任意给定的n，输出 1，2，…，n 的所有出栈顺序。

#include<bits/stdc++.h>
#include <deque>
#include <vector>
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair<int, int>
#define x first
#define y second
const int maxl = 1e6 + 7;

int n, cnt = 1;
vector<int> path;
deque<int> st;

void dfs(int i) {
    if (i == n + 1) {
        if (cnt > 20) return;
        for (int val : path) cout << val;
        for (int val : st) cout << val;
        cout << endl;
        cnt++;
        return;
    }

    // 删除栈顶元素
    if (!st.empty()) {
        int tp = st.front();
        st.pop_front();
        path.push_back(tp);
        dfs(i);
        st.push_front(tp);
        path.pop_back();
    }

    // 当前元素加入栈
    st.push_front(i);
    dfs(i + 1);
    st.pop_front();


}

void slove() {
    cin >> n;
    dfs(1);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    /*cin >> t;*/
    while(t--) slove();
    return 0;
}

## 2

有 n 个任务和 m 个工人。每个任务有一个难度值，每个工人有一个能力值。如果一个工人的能力值大于或等于某个任务的难度值，那么这个工人就可以完成这个任务。现在有 x 个工具，每个工具可以提升一个工人 y 点能力值。请问如何分配这些工具，才能使得工人们最多完成多少个任务？

这题不会，贪心过了 44.4%，就不放代码了

3 动态规划（完全背包，leetcode原题 322.零钱兑换）

这个题面就不写了，自己找原题把，下面是我的代码。

#include<bits/stdc++.h>
#include <cstring>
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair<int, int>
#define x first
#define y second
const int maxl = 1e6 + 7;

int n, m;
int a[maxl];
int dp[maxl];

void slove() {
    memset(dp, 0x3f, sizeof(dp));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= m; j++) {
            dp[j] = min(dp[j], dp[j - a[i]] + 1);
        }
    }
    if (dp[m] > m) cout << 0 << endl; // 这里要输出 0
    else cout << dp[m] << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    /*cin >> t;*/
    while(t--) slove();
    return 0;
}