笔试时间：2025年5月10日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：消去字符

有一个长度为 n 的字符串 s，你可以删除其中的 m 个字符，使剩余字符串的字典序最小，输出这个字符串。

输入描述

第一行输入一个整数 T，代表接下来有 T组测试数据。

对于每一组测试数据，第一行输入两个数 n, m 代表字符串的长度和可以删除的字符数量。

接下来输入长度为 n 的字符串。

1 ≤ T ≤ 5

2 ≤ n ≤ 100000

1 ≤ m < n

输出描述

对于每一组数据，输出一个答案。

样例输入

2

5 2

abcab

10 4

lkqijxsnny

样例输出

aab

ijsnny

参考题解

单调栈，遍历字符串，如果当前字符比栈顶字符小且还有剩余删除次数 ，则弹出栈顶字符，直到无法继续删除或栈为空。遍历结束后，如果仍有剩余的删除次数，直接从栈末尾删除剩余次数对应的字符。

C++：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        string s;
        cin >> n >> m >> s;
        vector<char> stk;
        for (auto& c : s) {
            while (m && !stk.empty() && stk.back() > c) {
                m -= 1;
                stk.pop_back();
            }
            stk.push_back(c);
        }
        if (m) {
            stk.resize(stk.size() - m);
        }
        cout << string(begin(stk), end(stk)) << '\n';
    }
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            String s = sc.next();
            LinkedList<Character> stk = new LinkedList<>();
            for (char c : s.toCharArray()) {
                while (m > 0 && !stk.isEmpty() && stk.getLast() > c) {
                    m--;
                    stk.removeLast();
                }
                stk.add(c);
            }
            while (m > 0) {
                stk.removeLast();
                m--;
            }
            StringBuilder result = new StringBuilder();
            for (char c : stk) {
                result.append(c);
            }
            System.out.println(result.toString());
        }
        sc.close();
    }
}

Python：

def main():
    t = int(input())
    for _ in range(t):
        n, m, s = input().split()
        n, m = int(n), int(m)
        stk = []
        for c in s:
            while m > 0 and stk and stk[-1] > c:
                m -= 1
                stk.pop()
            stk.append(c)
        if m > 0:
            stk = stk[:-m]
        print(''.join(stk))

if __name__ == "__main__":
    main()

第二题：每日任务

小明被安排了 n 个每日任务，小明每天必须完成一个才能下班。

每个任务都有一个完成的时间 ti，小明的 leader 每天会加大其他任务的难度，会让第 x 个任务的完成时间增加 c。

你需要输出每次修改后，小明这天的最短下班时间。

初始时所有的任务完成时间为 1。

注：每个任务在每天都可以选择。

输入描述

第一行输入两个整数 n, m，表示任务数量和天数 (1 ≤ n, m ≤ 10^5)

接下来 m 行，每行两个整数 xi, ci，表示第 xi 个任务完成时间增加 ci (1 ≤ xi ≤ n, 1 ≤ ci ≤ 10^5)

输出描述

对于每天的修改，需输出出这天下班的最短时间。

样例输入

3 9

1 1

1 1

2 1

2 1

2 1

3 1

1 1

2 1

3 1

样例输出

1

1

1

1

1

2

2

2

3

参考题解

map。利用map维护所有完成时间出现的次数。每次修改就在map中更新对应次数的出现数量，询问最小值就输出map中最小的键即可。

C++：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1, 1);
    map<int, int> mp;
    mp[1] = n;
    for (int i = 0; i < m; ++i) {
        int x, c;
        cin >> x >> c;
        mp[a[x]] -= 1;
        if (!mp[a[x]]) {
            mp.erase(a[x]);
        }
        a[x] += c;
        mp[a[x]] += 1;
        cout << mp.begin()->first << '\n';
    }
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n + 1];
        Arr