笔试时间：2024年03月31日

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

第一题

题目：米小游与—番赏2.0

本题目由抽崩坏三茶歇时刻—番赏真实事件改(乱)编!

一番赏初始有n个抽赏，有m个人排队购买，在队列最前面的人可以购买1个抽赏，买完之后这个人可以再次排队。

每一个抽赏都对应一个从'A'到'I'之间的大写字母，A赏比B赏稀有，B赏比C赏稀有，以此类推。买走最后一个抽赏的人将额外获赠一个last赏，为了简化，我们将last赏计为S赏，S赏比A赏稀有。

米小游知道一个只由大写字母组成的字符串s，表示购买第i个抽赏可以获得赏，她也知道排队购买抽赏的顺序数组a，表示购买i个抽赏的是第个人。米小游想知道每个人抽到了哪些赏，按稀有度排序，最稀有的排在最前面。(数据保证每个人至少购买了1个抽赏)。

输入描述

第—行输入两个整数n,m，表示抽赏个数、人数；

第二行输入一个长度为n的只由'A'到'I'之间的大写字母组成的字符串s；

第三行输入一个长度为n的数组a，表示排队购买抽赏的顺序数组。

输出描述

输出m行，每行输出一个字符串表示第i个人获得的抽赏，按稀有度顺序排序。

样例输入一

3 2

CAB

1 1 2

样例输出一

ACSB

第1个人购买了第1个抽赏，为C赏。第1个人购买了第2个抽赏，为A赏。

第2个人购买了第3个抽赏，为B赏，并获赠一个last赏，计为S赏。第1个人获得的抽赏为AC。(A赏比C赏稀有)

第1个人获得的抽赏为SB。(S赏比B赏稀有)

样例输入二

65

ABCDEA

1 2 3 4 5 1

样例输出二

SAA

B

C

D

E

参考题解

统计每个人得到的抽赏集合，再按照字典序排序即可。

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<vector<char>> ans(n);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        ans[a - 1].push_back(s[i]);
        if (i == n - 1) {
            ans[a - 1].push_back('S');
        }
    }
    for (int i = 0; i < n; ++i) {
        sort(ans[i].begin(), ans[i].end(), [&](auto a, auto b) {
            if (a == 'S') return true;
            if (b == 'S') return false;
            return a < b;
        });
        for (char c : ans[i]) cout << c;
        cout << "\n";
    }

}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String s = scanner.next();
        List<List<Character>> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            int a = scanner.nextInt();
            while (ans.size() < a) {
                ans.add(new ArrayList<>());
            }
            ans.get(a - 1).add(s.charAt(i));
            if (i == n - 1) {
                ans.get(a - 1).add('S');
            }
        }
        for (int i = 0; i < n; ++i) {
            Collections.sort(ans.get(i), (a, b) -> {
                if (a == 'S') return 1;
                if (b == 'S') return -1;
                return Character.compare(a, b);
            });
            for (char c : ans.get(i)) System.out.print(c);
            System.out.println();
        }
    }
}

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

n, m = map(int, input().split())
s = input()
ans = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    ans[a - 1].append(s[i])
    if i == n - 1:
        ans[a - 1].append('S')

for i in range(n):
    ans[i].sort(key=lambda x: x if x != 'S' else '', reverse=True)
    print(''.join(ans[i]))

第二题

题目：米小游的遗器

米小游有n个遗器，遗器共有m种类型，每个遗器有一个分数α和类型b。米小游最喜欢的角色是三月七，为了合成适合三月七的遗器，米小游准备分解掉不需要的遗器，但她需要保留k个遗器，且每种类型的遗器都至少要保留一个。米小游想知道她能保留的k个遗器的总分最高是多少。

输入描述

第一行输入三个整数n,m,k表示遗器个数、遗器类型、要保留的遗器个数。

接下来n行，每行输入两个整数表示遗器a,b，数据保证每种类型的遗器至少有1个。

输出描述

输出一个整数表示答案。

样例输入

4 2 3

1 1

1 2

2 1

2 2

样例输出

5

说明：

保留第2、3、4个遗器，或保留第1、3、4个遗器。

参考题解

使用最大堆排序，剩余的遗器中选择分数最大的几个

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

#include <functional>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
using ll = long long;
using iter = vector<int>::iterator;
using P = pair<iter, int>;

int main() {
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>> arr(n);
    unordered_map<int, vector<int>> g;
    for (int i = 0; i < n; ++i) {
        int a, b; cin >> a >> b;
        g[b].push_back(a);
    }
    ll ans = 0, sz = k - g.size();
    auto cmp = [](P& a, P& b){
        return *a.first < *b.first;
    };
    priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);
    for (auto& [k, v] : g) {
        sort(v.begin(), v.end(), greater<>());
        ans += v[0];
        if (v.size() > 1)
            pq.push({v.begin() + 1, k});
    }
    while (sz) {
        auto [it, k] = pq.top(); pq.pop();
        ans += *it;
        it++;
        if (it != g[k].end()) pq.push({it, k});
        --sz;
    }
    cout << ans;
}

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

import java.util.*;

public class Main {
    static class Pair {
        ListIterator<Integer> iter;
        int value;

        Pair(ListIterator<Integer> iter, int value) {
            this.iter = iter;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>(n);
        HashMap<Integer, ArrayList<Integer>> g = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int a