✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线70+套真题改编解析，后续会持续更新的

春秋招合集 -> 互联网必备刷题宝典🔗

题目一：精简字符串

1️⃣：使用单调栈维护当前保留的字符

2️⃣：遍历字符串，当栈顶字符大于当前字符且可删除时弹出栈顶

3️⃣：处理剩余可删除字符，输出最终栈内元素

难度：中等

这道题目的关键在于理解删除某些字符使字典序最小的策略。使用单调栈可以有效地保留较小的字符在较前的位置，从而保证字典序最小，实现了O(n)的时间复杂度。

题目二：每日任务优化

1️⃣：维护每个任务的当前完成时间

2️⃣：使用有序数据结构存储所有任务时间

3️⃣：每次修改后快速找出最小完成时间

难度：中等

这道题目考察了对有序数据结构的使用，关键是在每次修改后能够快速找出最小值。通过维护一个有序集合，我们可以在O(log n)时间内完成每次查询，总体时间复杂度为O((n+m)log n)。

题目三：忍者屋顶之旅

1️⃣：使用动态规划，维护到达每个位置的最小时间

2️⃣：考虑三种移动方式的状态转移

3️⃣：处理每列内上下跳转的特殊情况

难度：中等偏难

这道题目是一个经典的动态规划问题，难点在于正确处理多种移动方式的状态转移和同列内的上下跳转。通过定义合适的状态和转移方程，可以在O(n)的时间复杂度内解决，对于较大的数据范围也能高效处理。

01. 精简字符串

问题描述

小柯是一名数据分析师，她正在处理一份古老的档案文件。这份档案由于年代久远，上面的部分文字变得模糊不清。小柯决定删除一些无法辨认的字符，以保留最有价值的信息。

具体来说，她有一份长度为 的字符串文档，她需要从中删除恰好 个字符，使得剩余的字符串按照字典序最小。字典序是指按照字母表顺序比较两个字符串的大小，例如 "abc" 的字典序小于 "abd"。

请你帮助小柯找出删除 个字符后字典序最小的字符串。

输入格式

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

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

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

输出格式

对于每一组数据，输出一个字符串，表示删除 个字符后字典序最小的剩余字符串。

样例输入

2
5 2
abcab
10 4
lkqijxsnny

样例输出

aab
ijsnny

数据范围

• 
• 
• 

样例 解释说明

样例1	在字符串"abcab"中删除2个字符，可以得到"aab"，这是所有可能结果中字典序最小的
样例2	在字符串"lkqijxsnny"中删除4个字符，得到"ijsnny"是字典序最小的结果

题解

这道题目要求我们从一个长度为 n 的字符串中删除 m 个字符，使得剩余的字符串字典序最小。

解题思路其实很直观：我们希望尽可能保留越小的字符在越前面的位置。这启发我们使用单调栈的思想来解决这个问题。

算法步骤

1. 维护一个栈，表示当前保留的字符
2. 遍历字符串中的每个字符：
   • 如果当前栈不为空且栈顶字符大于当前字符，并且我们还可以删除字符（m > 0），则弹出栈顶字符，m 减 1
   • 重复上述过程，直到不满足条件
   • 将当前字符入栈
3. 遍历结束后，如果 m 仍然大于 0，则从栈的尾部删除剩余的 m 个字符
4. 栈中剩余的字符组成的字符串即为答案

这个算法能够保证栈中的字符始终保持单调不减的顺序，同时优先删除较大的字符，从而保证字典序最小。

时间复杂度分析

• 每个字符最多入栈和出栈一次，因此时间复杂度为 O(n)
• 空间复杂度为 O(n)，用于存储栈

这个方法对于给定的 n ≤ 100000 的数据范围非常高效，能够快速处理所有测试用例。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def min_lexical_string(s, n, m):
    # 使用列表作为栈
    stk = []
    
    # 遍历字符串
    for c in s:
        # 当栈不为空且可删除字符数>0且栈顶>当前字符时，弹出栈顶
        while stk and m > 0 and stk[-1] > c:
            stk.pop()
            m -= 1
        stk.append(c)
    
    # 如果还能删除字符，从尾部删除
    while m > 0 and stk:
        stk.pop()
        m -= 1
    
    # 返回结果
    return ''.join(stk)

# 读取测试用例数
t = int(input())
for _ in range(t):
    # 读取n和m
    n, m = map(int, input().split())
    s = input()
    
    # 输出结果
    print(min_lexical_string(s, n, m))

• Cpp

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

string min_lex_str(const string& s, int n, int m) {
    vector<char> stk;
    
    // 遍历字符串
    for (char c : s) {
        // 当栈不为空且可删除字符数>0且栈顶>当前字符时，弹出栈顶
        while (!stk.empty() && m > 0 && stk.back() > c) {
            stk.pop_back();
            m--;
        }
        stk.push_back(c);
    }
    
    // 如果还能删除字符，从尾部删除
    while (m > 0 && !stk.empty()) {
        stk.pop_back();
        m--;
    }
    
    // 返回结果
    return string(stk.begin(), stk.end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m;
        string s;
        cin >> n >> m >> s;
        
        cout << min_lex_str(s, n, m) << '\n';
    }
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            String[] nm = br.readLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            String s = br.readLine();
            
            System.out.println(minLexStr(s, n, m));
        }
    }
    
    private static String minLexStr(String s, int n, int m) {
        Deque<Character> stk = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            while (!stk.isEmpty() && m > 0 && stk.peekLast() > c) {
                stk.removeLast();
                m--;
            }
            stk.addLast(c);
        }
        
        // 如果还能删除字符，从尾部删除
        while (m > 0 && !stk.isEmpty()) {
            stk.removeLast();
            m--;
        }
        
        // 构建结果字符串
        StringBuilder res = new StringBuilder();
        for (char c : stk) {
            res.append(c);
        }
        
        return res.toString();
    }
}

02. 每日任务优化

问题描述

小毛是一家科技公司的员工，他每天都需要完成公司安排的任务才能下班。公司总共给他安排了 个固定的任务选项，他每天必须从中选择并完成一个。

初始时，每个任务的完成时间都是 个小时。然而，公司的管理层喜欢不断调整任务难度。每天，他们会选择第 个任务，将其完成时间增加 个小时。

小毛是个聪明人，他每天都会选择完成时间最短的任务，以便尽早下班。请你帮他计算，在每次任务调整后，他当天最早可以在多少小时后下班。

输入格式

第一行输入两个整数 、，表示任务数量和天数。

接下来 行，每行两个整数 、，表示第 天第 个任务完成时间增加 小时。

输出格式

对于每天的修改，输出一个整数，表示小毛那天最早可以在多少小时后下班。

样例输入

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

数据范围

• 
• 
• 

样例 解释说明

样例1	初始时所有任务完成时间都是1小时。第1天增加第1个任务时间后变成[2,1,1]，小毛选择第2或第3个任务，用时1小时。以此类推，直到第6天所有任务的完成时间变为[3,4,2]，他选择第3个任务，用时2小时。最后一天后，任务时间为[4,5,4]，最少用时3小时。

题解

这道题目讲的是每天必须完成n个任务中的一个才能下班，每天会修改一个任务的完成时间，我们需要在每次修改后计算当天可以最早多少小时下班。

解题的关键是：我们需要维护所有任务的完成时间，并在每次修改后快速找出最小值。

解题思路

想要快速找出一组数据中的最小值，一般有两种常见方法：

1. 维护一个有序数据结构
2. 使用优先队列（最小堆）

在这道题中，我们使用了有序集合（如C++的multiset，Java的TreeSet）来存储所有任务的完成时间。这样我们可以在O(log n)的时间内完成以下操作：

• 删除特定值
• 插入新值
• 获取最小值

算法步骤

1. 初始化一个大小为n的数组t，用于存储每个任务的当前完成时间，初始值都为1
2. 初始化一个有序集合ms，包含n个初始值1
3. 对于每次修改操作(x, c)：
   • 从集合中删除t[x]的旧值
   • 更新t[x] += c
   • 将新的t[x]插入集合
   • 输出集合的最小值，即*ms.begin()

时间复杂度分析

• 初始化时间：O(n)
• 每次修改操作：O(log n)
• 总时间复杂度：O((n+m) log n)，其中n是任务数量，m是修改次数

这个时间复杂度对于给定的条件（n, m < 10^5）是完全可以接受的。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

# 读取任务数量和天数
n, m = map(int, input().split())

# 初始化任务时间数组（下标从1开始）
task = [1] * (n + 1)

# 使用列表和排序模拟有序集合（效率较低但实现简单）
times = [1] * n

# 处理每天的任务修改
for _ in range(m):
    x, c = map(int, input().split())
    
    # 更新任务时间
    task[x] += c
    
    # 重建时间列表
    times = [task[i] for i in range(1, n + 1)]
    times.sort()
    
    # 输出最短时间
    print(times[0])

• Cpp

#include <iostream>
#include <vector>
#i