笔试时间：2025年03月15日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：Monica的音乐延长

Monica听到了一串音乐，她把音乐的音调用字符串表示:C表示do，D表示re，E表示mi，F表示fa，G表示sol，A表示la，B表示xi。当有一个长音时，Monica用多个相同的字母来表示音的时间长度。例如，CCCCABCC代表共有4个音，其中有一个长度为1的do，一个长度为1的la，一个长度为1的xi，一个长度为2的do。Monica共有k次操作，每次操作会选择一个音，将其时间延长10单位长度。Monica希望最终时间长度最短的那个音长度尽可能长，你能帮帮她吗？你需要给出Monica一个操作方案，并输出最终的每个音长，详细见样例输出。

输入描述

第一行输入一个长度不超过200000的字符串，代表Monica听到的音乐。字符串保证仅包含'A'~'G'这七种字母。

第二行输入一个正整数k，代表Monica的操作次数。

输出描述

首先输出k行，每行输出一个正整数x和一个字符ch，代表Monica对第x个音进行操作，该音的音调为ch

。最后输出一个字符串，形式为ch1(len1)ch2(len2)，用来表示最终操作后，每个音和该音的长度。如果有多种不同的操作方案，输出任意即可。但需要保证最终音长的最小值是尽可能大的。

样例输入

CCABCC

3

样例输出

2 A

3 B

2 A

C(2)A(21)B(11)C(2)

说明：

共操作3次。

对第二个音la操作1次，长度变成11。

对第三个音xi操作1次，长度变成11。

对第二个音la操作1次，长度变成21。

操作结束后，音长的最小值为2。可以证明，这个最小值是尽可能大的，即音长最小值不可能超过2。

参考题解

优先队列，首先将相同的连续字符进行合并，将他们合并成一个音，然后通过优先队列的方式，

每次查找字符最少的，将字符出现出现+10之后重新放入优先队列，重复op次操作输出即可。

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

#include<bits/stdc++.h>
using namespace std;
struct Compare {
    bool operator()(const tuple<int, char, int>& a, const tuple<int, char, int>& b) {
        if (get<0>(a) != get<0>(b)) {
            return get<0>(a) > get<0>(b);
        }
        return get<1>(a) > get<1>(b);
    }
};
int main() {
    string s;
    int op;
    cin >> s;
    cin >> op;
    unordered_map<int, int> mp;
    unordered_map<int, char> which;
    priority_queue<tuple<int, char, int>, vector<tuple<int, char, int>>, Compare> que;
    int id = 1;
    int i = 0;
    while (i < s.length()) {
        int j = i;
        while (j + 1 < s.length() && s[j + 1] == s[j]) {
            j++;
        }
        int cnt = j - i + 1;
        que.push(make_tuple(cnt, s[j], id));
        mp[id] = cnt;
        which[id] = s[j];
        id++;
        i = j + 1;
    }
    for (int k = 0; k < op; k++) {
        auto [cnt, ch, d] = que.top();
        que.pop();
        cout << d << " " << ch << endl;
        que.push(make_tuple(cnt + 10, ch, d));
        mp[d] += 10;
    }
    string res;
    for (int k = 1; k < id; k++) {
        res += which[k];
        res += "(";
        res += to_string(mp[k]);
        res += ")";
    }
    cout << res << endl;
    return 0;
}

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

import java.util.*;

public class Main {
    static class Group {
        int count;
        char ch;
        int id;

        Group(int count, char ch, int id) {
            this.count = count;
            this.ch = ch;
            this.id = id;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int op = sc.nextInt();

        Map<Integer, Integer> mp = new HashMap<>();
        Map<Integer, Character> which = new HashMap<>();

        PriorityQueue<Group> pq = new PriorityQueue<>((a, b) -> {
            if (a.count != b.count) return b.count - a.count;
            return a.ch - b.ch;
        });

        int id = 1;
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j + 1 < s.length() && s.charAt(j + 1) == s.charAt(j)) {
                j++;
            }
            int cnt = j - i + 1;
            char ch = s.charAt(j);
            pq.add(new Group(cnt, ch, id));
            mp.put(id, cnt);
            which.put(id, ch);
            id++;
            i = j + 1;
        }

        for (int k = 0; k < op; k++) {
            Group top = pq.poll();
            System.out.println(to