✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

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

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

题目一：密码箱的最优开启顺序

1️⃣：使用贪心算法结合栈维护字典序最小的子序列

2️⃣：通过统计剩余次数来判断是否可以"反悔"选择更小的数字

3️⃣：利用栈的性质保证子序列的字典序最小

难度：中等

这道题目是经典的字典序最小不重复子序列问题。关键在于理解贪心策略：当遇到更小的数字时，如果之前选择的较大数字在后面还会出现，就可以"反悔"，先选择当前的较小数字。通过栈和计数数组的配合，可以在 O(n) 时间内得到最优解。

题目二：古籍修复的编码验证

1️⃣：将每个数字转换为对应的二进制字符串表示

2️⃣：使用深度优先搜索枚举所有可能的匹配方案

3️⃣：通过优先处理候选较少的数字来优化搜索效率

难度：中等

这道题目结合了字符串匹配和搜索算法。核心难点在于需要找到互不重叠的匹配区间。虽然问题规模较小，但需要仔细设计搜索策略和剪枝方法。通过位集快速判断区间冲突，并按匹配数量排序来减少搜索空间，可以高效解决问题。

01. 密码箱的最优开启顺序

问题描述

小基 正在参加一个密室逃脱游戏，她发现了一个神秘的密码箱。这个密码箱有一个特殊的开启机制：箱子上有 个按钮，每个按钮上都标有一个数字，范围在 到 之间。游戏规则告诉她， 到 这些数字在按钮上都至少出现过一次。

为了打开密码箱，小基 需要按照特定的顺序按下一些按钮，使得：

1. 每个数字 到 都恰好被按一次
2. 按下按钮的顺序（从左到右）形成的数字序列在字典序上是最小的
3. 按下的按钮必须保持它们在原序列中的相对位置（即只能选择子序列）

小基 想要尽快解开这个谜题，你能帮助她找到最优的按钮按下顺序吗？

输入格式

第一行包含两个正整数 和 ，分别表示按钮的总数和数字的种类数。

第二行包含 个正整数 ，表示每个按钮上的数字。

输出格式

输出一行包含 个数字，表示字典序最小的按钮按下顺序。数字之间用空格分隔，行末不要有多余的空格。

样例输入

5 3
2 1 3 3 2

样例输出

1 3 2

数据范围

题解

这道题本质上是要找字典序最小的不重复子序列。

核心思路是使用贪心 + 栈的方法：我们希望每次选择的数字尽可能小，但同时要保证后续还能找到所有需要的数字。

具体算法步骤：

1. 先统计每个数字在剩余序列中的出现次数
2. 用一个栈来维护当前的答案序列，用一个标记数组记录哪些数字已经被选入答案
3. 遍历输入序列，对于每个数字：
   • 先将其剩余次数减1
   • 如果这个数字已经在答案中，跳过
   • 否则，检查栈顶元素：如果栈顶比当前数字大，且栈顶数字在后面还会出现，就可以弹出栈顶来获得更小的字典序
   • 将当前数字加入栈中并标记为已选择

这样做的原理是：我们总是贪心地选择当前能选的最小数字，同时通过栈的性质保证字典序最小。当发现一个更小的数字时，如果前面选择的较大数字在后面还会出现，我们就可以"反悔"，先选择较小的数字。

时间复杂度为 ，因为每个元素最多入栈出栈一次。

参考代码

• Python

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

n, k = map(int, input().split())
a = list(map(int, input().split()))

# 统计每个数字剩余出现次数
cnt = [0] * (k + 1)
for x in a:
    cnt[x] += 1

stk = []  # 答案栈
used = [False] * (k + 1)  # 是否已被选择

for x in a:
    cnt[x] -= 1  # 消费一次出现
    if used[x]:  # 已选择过，跳过
        continue
    
    # 贪心调整：如果栈顶更大且后面还有，就弹出
    while stk and stk[-1] > x and cnt[stk[-1]] > 0:
        used[stk[-1]] = False
        stk.pop()
    
    # 加入当前数字
    stk.append(x)
    used[x] = True

print(' '.join(map(str, stk)))

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 统计剩余次数
    vector<int> rem(k + 1, 0);
    for (int x : a) rem[x]++;
    
    vector<int> res;  // 结果序列
    vector<bool> vis(k + 1, false);  // 访问标记
    
    for (int x : a) {
        rem[x]--;  // 减少剩余次数
        if (vis[x]) continue;  // 已选择
        
        // 调整栈顶元素
        while (!res.empty() && res.back() > x && rem[res.back()] > 0) {
            vis[res.back()] = false;
            res.pop_back();
        }
        
        res.push_back(x);
        vis[x] = true;
    }
    
    // 输出结果
    for (int i = 0; i < (int)res.size(); i++) {
        if (i > 0) cout << " ";
        cout << res[i];
    }
    cout << "\n";
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        // 统计每个数字剩余次数
        int[] remCnt = new int[k + 1];
        for (int x : a) {
            remCnt[x]++;
        }
        
        List<Integer> ans = new ArrayList<>();  // 答案列表
        boolean[] inAns = new boolean[k + 1];   // 是否在答案中
        
        for (int x : a) {
            remCnt[x]--;  // 消费一次
            if (inAns[x]) continue;  // 已在答案中
            
            // 贪心弹出更大的元素
            while (!ans.isEmpty() && ans.get(ans.size() - 1) > x 
                   && remCnt[ans.get(ans.size() - 1)] > 0) {
                int last = ans.remove(ans.size() - 1);
                inAns[last] = false;
            }
            
            ans.add(x);
            inAns[x] = true;
        }
        
        // 输出答案
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.size(); i++) {
            if (i > 0) sb.append(" ");
            sb.append(ans.get(i));
        }
        System.out.println(sb.toString());
    }
}

02. 古籍修复的编码验证

问题描述

小毛是一位古籍修复专家，最近他在整理一批古代密码文献。这些古籍中记录了一种特殊的编码方式：每个重要信息都被转换为特定的二进制编码保存在长条形的编码带中。

编码带是一个由 和 组成的长串，如 。现在小毛手中有 个需要验证的重要信息，每个信息都对应一个整数，需要验证这些整数的二进制表示（不含前导零，特别地， 的二进制表示就是 ）能否在编码带中找到对应的连续片段。

关键的约束是：选择的编码片段必须互不重叠，因为古人设计这种编码时，每个位置的信息只能被使用一次。

小毛想知道，给定的编码带是否能够同时验证所有的重要信息。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 ，表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个正整数 和 ，分别表示编码带的长度和需要验证的信息数量
• 第二行包含一个长度为 的字符串 ，由字符 和 组成，表示编码带
• 第三行包含 个非负整数 ，表示需要验证的重要信息

输出格式

对于每组测试数据，如果所有信息都能在编码带中找到对应的互不重叠的二进制片段，输出 YES；否则输出 NO。

样例输入

2
5 2
10110
2 1
5 1
00000
1

样例输出

YES
NO

数据范围

题解

这是一个典型的匹配问题，需要为每个数字的二进制表示在字符串中找到互不重叠的匹配位置。

由于数据规模较小（，），可以使用深度优先搜索来解决：

1. 预处理阶段：

   • 将每个数字转换为二进制字符串（注意0的特殊处理）
   • 在编码带中找出每个二进制字符串的所有可能匹配位置

2. 搜索策略：

   • 使用DFS枚举所有可能的匹配方案
   • 为了减少搜索空间，优先处理候选位置较少的数字
   • 使用位集（bitset）来快速判断区间是否重叠

3. 剪枝优化：

   • 如果某个数字完全无法匹配，直接返回NO
   • 选择匹配位置时，只考虑与已选择区间不重叠的位置

这种方法的时间复杂度在最坏情况下是指数级的，但由于实际的约束条件（区间不能重叠、m很小），运行效率很高。

参考代码

• Python

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

def get_binary(num):
    # 获取数字的二进