笔试时间：2024年08月10日 后端笔试

历史笔试传送门：2023秋招笔试合集

第一题

题目：小美的密码

小美准备登录美团，需要输入密码，小美忘记了密码，只记得密码可能是 n个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串，对于相同长度的字符串，小美随机尝试，并且相同的密码只会尝试一次。小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次才能登录成功。小美不会重新尝试已经尝试过的字符串。成功登录后会立即停止尝试。

输入描述

第一行输入一个整数 n(1<=n<=1000)代表密码字符串的个数。

第二行输入一个只由小写字母组成的字符串 s(1<=|s|<=1000)代表正确的密码。

接下来 n 行，每行输入一个长度不超过 1000的字符串，代表小美记得的密码。

输出描述

在一行上输出两个整数，表示最少和最多尝试次数。

样例输入

4

ab

abc

ab

ac

ac

样例输出

1 2

说明

小美可能按照 ["ab", "ac", "abc"] 的顺序尝试，第一次尝试成功，也可能按照 ["ac", "ab", "abc"] 的顺序尝试，第二次尝试成功。

小美在尝试 "ac" 发现不正确后不会继续尝试 "ac"。

参考题解

哈希表

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    string ans;
    cin >> ans;
    
    unordered_map<int, set<string>> pos;
    for (int i = 0; i < n; ++i) {
        string p;
        cin >> p;
        pos[p.size()].insert(p);
    }
    
    vector<pair<int, set<string>>> sorted_pos(pos.begin(), pos.end());
    sort(sorted_pos.begin(), sorted_pos.end());
    
    int step = 0;
    int MIN = -1, MAX = -1;
    for (const auto& [k, v] : sorted_pos) {
        if (v.find(ans) != v.end()) {
            MIN = step + 1;
            MAX = step + v.size();
        } else {
            step += v.size();
        }
    }
    
    cout << MIN << " " << MAX << endl;
    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        String ans = scanner.next();
        
        Map<Integer, Set<String>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String p = scanner.next();
            pos.computeIfAbsent(p.length(), k -> new HashSet<>()).add(p);
        }
        
        List<Map.Entry<Integer, Set<String>>> sortedPos = new ArrayList<>(pos.entrySet());
        sortedPos.sort(Map.Entry.comparingByKey());
        
        int step = 0;
        int MIN = -1, MAX = -1;
        for (Map.Entry<Integer, Set<String>> entry : sortedPos) {
            Set<String> v = entry.getValue();
            if (v.contains(ans)) {
                MIN = step + 1;
                MAX = step + v.size();
            } else {
                step += v.size();
            }
        }
        
        System.out.println(MIN + " " + MAX);
        
        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

from collections import defaultdict

n = int(input())
ans = input()

pos = defaultdict(set)
for _ in range(n):
    p = input()
    pos[len(p)].add(p)

pos = dict(sorted(pos.items()))

step = 0
MIN,MAX = -1,-1
for k,v in pos.items():
    if ans in v:
        MIN =step + 1
        MAX = step + len(v)
    else:
        step += len(v)

print(MIN, MAX)

第二题

题目：小美的数组删除

小美有一个长度为 n 的数组 a1,a2,....,an ，他可以对数组进行如下操作：

• 删除第一个元素 a1，同时数组的长度减一，花费为 x。
• 删除整个数组，花费为 k*MEX(a) （其中 MEX(a) 表示 a 中未出现过的最小非负整数。例如 [0,1,2,4] 的 MEX 为 3 ）。

小美想知道将 a 数组全部清空的最小代价是多少，请你帮帮他吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1<=T<=1000) 代表数据组数，每组测试数据描述如下：

第一行输入三个正整数 n,k,x(1<=n<=2*10^5, 1<=k,x<=10^9) 代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。

第二行输入 n 个整数 a1,a2,....,an(0<=ai<=n)，表示数组元素。

除此之外，保证所有的 n 之和不超过 2*10^5。

输出描述

对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

样例输入

1

6 3 3

4 5 2 3 1 0

样例输出

15

说明：

若不执行操作一就全部删除，MEX{4,5,2,3,1,0} = 6，花费 18 ；

若执行一次操作一后全部删除，MEX{5,2,3,1,0} = 4，花费 3+12；

若执行两次操作一后全部删除，MEX{2,3,1,0} = 4，花费 6+12 ；

若执行三次操作一后全部删除，MEX{3,1,0} = 2，花费 9+6 ；

若执行四次操作一后全部删除，MEX{1,0} = 2，花费 12+6 ；

若执行五次操作一后全部删除，MEX{0} = 1，花费 15+3；

若执行六次操作一，MEX{} = 0，花费 18；

参考题解

动态规划+维护动态最小未出现的整数。f[i]表示从i往后考虑的最小花费，选择就是选择第一个元素或者直接删除后续所有的元素。对于删除后续所有的元素的选项，我们必须要直到MEX是多少，我们可以用在更新dp的过程中，用一个suffix不断地更新当前的最小未出现的整数。虽然这里出现了两层循环的嵌套，但是并不会重置参数，因此复杂度是O(n).

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long n, k, x;
        cin >> n >> k >> x;
        
        vector<long long> A(n);
        for (int i = 0; i < n; ++i) {
            cin >> A[i];
        }
        
        vector<long long> dp(n + 1, LLONG_MAX);
        dp[n] = 0;
        
        set<int> vst;
        int suffix_MEX = 0;
        
        for (int i = n - 1; i >= 0; --i) {
            vst.insert(A[i]);
            while (vst.count(suffix_MEX)) {
                suffix_MEX++;
            }
            dp[i] = min(dp[i + 1] + x, k * suffix_MEX);
        }
        
        cout << dp[0] << endl;
    }
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(Strin