✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

得物

题目一：魔法药剂调配

1️⃣：统计每种元素在所有配方中的出现次数

2️⃣：找到每种元素的最小出现次数

3️⃣：按字典序构造基础配方

难度：中等

这道题目的关键在于理解等效配方的概念，并发现问题本质是求所有配方的公共元素。通过统计字符频次并取最小值，可以得到一个 O(∑|s_i|) 的高效解法。

题目二：音乐厅演奏计划

1️⃣：设计三维动态规划状态

2️⃣：分情况讨论状态转移

3️⃣：使用滚动数组优化空间复杂度

难度：中等

这道题目考查动态规划的状态设计和转移。关键在于区分前一天是否练习的状态，以及正确处理打破原则的机会消耗。通过合理的状态定义，可以实现 O(nk) 的时间复杂度。

题目三：图书馆智能管理系统

1️⃣：理解双端存储系统的工作原理

2️⃣：维护指针位置和存储区大小

3️⃣：正确判断各种错误情况并输出对应信息

难度：中等偏难

这道题目需要准确模拟双端存储系统的各种操作，理解快速存取区和临时存放区的生长方向。通过维护指针和计数器，可以高效处理所有操作并检测错误情况，实现 O(n+m) 的时间复杂度。

01. 魔法药剂调配

问题描述

小兰是一位才华横溢的炼金术师，她正在研究古老的魔法药剂配方。在她的实验室里，每种药剂都是由不同的魔法元素组成的。

两种药剂被认为是等效的，当且仅当其中一种药剂可以通过重新排列魔法元素得到另一种药剂。例如，包含元素 的药剂和包含元素 的药剂是等效的，包含元素 的药剂和另一个包含元素 的药剂也是等效的，包含元素 的药剂和包含元素 的药剂等效。而包含元素 的药剂和包含元素 的药剂不等效，包含元素 的药剂和包含元素 的药剂不等效。

现在小兰收集了 种不同的药剂配方，每种配方都是由小写字母表示的魔法元素序列 组成。她希望找到一个最长的基础配方 ，使得每种药剂配方都能通过选取其中的一些元素（保持原有顺序）来形成与这个基础配方等效的药剂。

如果存在多个这样的基础配方，请输出字典序最小的配方。如果不存在这样的配方，则输出 。

输入格式

第一行输入一个正整数 ，表示数据组数。

对于每一组数据：

第一行输入一个正整数 ，表示药剂配方的个数。

第二行输入 个仅由小写字母组成的字符串 ，每两个字符串之间用一个空格隔开，末尾没有多余空格。

保证同一组数据的字符串长度之和不超过 。

输出格式

对于每一组数据，输出一行。如果有多个答案，请输出字典序最小的配方。如果找不到，则输出 。

样例输入

2
3
path photo hope
2
abc def

样例输出

hp
-1

数据范围

• 
• 
• 
• 保证同一组数据的字符串长度之和不超过

样例	解释说明
样例1	对于配方 path、photo、hope，字母 在三个配方中都至少出现1次，字母 在三个配方中都至少出现1次，因此基础配方为 。按字典序排列得到 。
样例2	对于配方 abc 和 def，没有任何公共的魔法元素，因此无法找到基础配方，输出 。

题解

这道题本质上是要找到所有配方的公共子序列中最长的一个。

考虑到两个配方等效的条件是可以重新排列元素，这意味着我们只关心每种元素的数量，而不关心它们的顺序。因此，问题转化为：找到一个元素组合，使得每种配方都包含足够数量的各种元素来形成这个组合。

具体分析如下：

1. 统计频次：对于每个配方，统计其中每种魔法元素（字母 到 ）的出现次数。

2. 找最小值：对于每种元素，找到它在所有配方中出现次数的最小值。这个最小值就是我们可以在基础配方中使用这种元素的最大次数。

3. 构造答案：将所有元素按字典序排列，每种元素重复其对应的最小次数，连接成最终的基础配方。

4. 特殊情况：如果所有元素的最小出现次数都为0，说明不存在公共元素，返回 。

时间复杂度为 ，空间复杂度为 （只需要常数大小的计数数组）。

参考代码

• Python

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

def solve():
    # 读取数据组数
    t = int(input())
    
    for _ in range(t):
        # 读取配方数量
        n = int(input())
        
        # 读取所有配方
        formulas = input().split()
        
        # 统计每个配方中各元素的出现次数
        cnt = []
        for formula in formulas:
            freq = [0] * 26  # 26个字母的频次
            for char in formula:
                freq[ord(char) - ord('a')] += 1
            cnt.append(freq)
        
        # 计算每种元素在所有配方中的最小出现次数
        min_freq = [float('inf')] * 26
        for i in range(26):
            for j in range(n):
                min_freq[i] = min(min_freq[i], cnt[j][i])
        
        # 构造基础配方
        result = ""
        for i in range(26):
            result += chr(ord('a') + i) * min_freq[i]
        
        # 输出结果
        if not result:
            print(-1)
        else:
            print(result)

solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        // 存储每个配方的元素频次
        vector<array<int, 26>> freq(n);
        
        for (int i = 0; i < n; i++) {
            string formula;
            cin >> formula;
            
            // 初始化频次数组
            freq[i].fill(0);
            
            // 统计每个元素的出现次数
            for (char ch : formula) {
                freq[i][ch - 'a']++;
            }
        }
        
        // 计算每种元素的最小出现次数
        array<int, 26> min_cnt;
        min_cnt.fill(INT_MAX);
        
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < n; j++) {
                min_cnt[i] = min(min_cnt[i], freq[j][i]);
            }
        }
        
        // 构造基础配方
        string ans = "";
        for (int i = 0; i < 26; i++) {
            ans.append(min_cnt[i], char('a' + i));
        }
        
        // 输出结果
        if (ans.empty()) {
            cout << -1 << '\n';
        } else {
            cout << ans << '\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));
        
        int testCases = Integer.parseInt(br.readLine());
        
        while (testCases-- > 0) {
            int numForm = Integer.parseInt(br.readLine());
            
            // 存储每个配方的元素频次
            int[][] elemFreq = new int[numForm][26];
            
            String[] formulas = br.readLine().split(" ");
            
            for (int i = 0; i < numForm; i++) {
                String formula = formulas[i];
                
                // 统计当前配方中每个元素的出现次数
                for (char ch : formula.toCharArray()) {
                    elemFreq[i][ch - 'a']++;
                }
            }
            
            // 计算每种元素在所有配方中的最小出现次数
            int[] minCount = new int[26];
            Arrays.fill(minCount, Integer.MAX_VALUE);
            
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < numForm; j++) {
                    minCount[i] = Math.min(minCount[i], elemFreq[j][i]);
                }
            }
            
            // 构造基础配方
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < minCount[i]; j++) {
                    result.append((char)('a' + i));
                }
            }
            
            // 输出结果
            if (result.length() == 0) {
                System.out.println(-1);
            } else {
                System.out.println(result.toString());
            }
        }
    }
}

02. 音乐厅演奏计划

问题描述

小基是一位杰出的钢琴家，她即将在接下来的 天里安排自己的演奏计划。作为一位专业的音乐家，小基深知过度练习可能会对手指造成损伤，因此她制定了一套严格的练习规则。

小基给自己定了一个原则：通常情况下，如果今天进行了高强度练习，那么明天就必须休息一天来让手指得到充分恢复。但是，小基也明白艺术创作有时需要灵感的连续迸发，所以她允许自己有 次特殊情况，可以在昨天已经进行高强度练习的情况下，今天继续进行高强度练习。

换句话说，小基每天最多进行一次高强度练习，原则上如果昨天练习了那么今天就不练习，但最多有 次打破原则的机会。

每次高强度练习都能为小基带来不同程度的艺术成就感，请帮小基规划一下练习计划来获得最大的成就感总和。

输入格式

第一行两个整数 和 ，表示小基正在计划未来 天的练习安排以及 次打破原则的机会。

第二行 个整数 ，其中 表示接下来第 天如果进行高强度练习可以获得的成就感数值。

输出格式

输出一行一个数，表示小基能在最佳练习计划下获得的成就感总和。

样例输入

7 1
1 2 3 4 5 6 7

样例输出

19

数据范围

样例	解释说明
样例1	最优的方案是选择第 天练习，并在第 天打破一次原则（因为第 天已经练过了，原则上不能继续练习，需要使用一次打破原则的机会），总成就感为 。

题解

这是一道经典的动态规划问题，关键在于状态的设计和转移。

我们可以用三维状态来描述问题： 表示考虑到第 天，已经使用了 次打破原则的机会，且前一天的状态为 （ 表示没有练习， 表示练习了）时能获得的最大成就感。

状态转移分析：

1. 第 天不练习： 无论前一天是否练习，今天都可以选择不练习。

   • 

2. 第 天练习： 需要分两种情况讨论

   • 前一天没练习： 可以直接练习，不需要消耗机会
     • 
   • 前一天练习了： 需要消耗一次打破原则的机会
     • 如果 ：

初始化： ，其余状态初始化为负无穷。

答案：

由于状态转移只依赖于前一天的状态，我们可以使用滚动数组优化空间复杂度。

时间复杂度：，空间复杂度：。

参考代码

• Python

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

def solve():
    # 读取输入
    n, k = map(int, input().split())
    scores = list(map(int, input().split()))
    
    # 使用无穷小值表示不可达状态
    NEG_INF = float('-inf')
    
    # prev[j][s] 表示上一天使用j次机会，状态为s的最大成就感
    # s=0表示没有练习，s=1表示练习了
    prev = [[NEG_INF, NEG_INF] for _ in range(k + 1)]
    prev[0][0] = 0  # 初始状态：第0天，使用0次机会，没有练习
    
    # 动态规划转移
    for day in range(1, n + 1):
        curr = [[NEG_INF, NEG_INF] for _ in range(k + 1)]
        
        for used in range(k + 1):
            # 今天不练习
            curr[used][0] = max(prev[used][0], prev[used][1])
            
            # 今天练习，前一天没练习
            if prev[used][0] != NEG_INF:
                curr[used][1] = max(curr[used][1], prev[used][0] + scores[day - 1])
            
            # 今天练习，前一天也练习（需要消耗一次机会）
            if used > 0 and prev[used - 1][1] != NEG_INF:
                curr[used][1] = max(curr[used][1], prev[used - 1][1] + scores[day - 1])
        
        prev = curr
    
    # 计算答案
    result = 0
    for used in range(k + 1):
        result = max(result, max(prev[used][0], prev[used][1]))
    
    print(result)

solve()

• Cpp

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

const long long NEG_INF = -1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    vector<int> score(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    
    // prev[j][s] 表示上一天使用j次机会，状态为s的最大成就感
    vector<array<long long, 2>> prev(k + 1), curr(k + 1);
    
    // 初始化
    for (int j = 0; j <= k; j++) {
        prev[j] = {NEG_INF, NEG_INF};
    }
    prev[0][0] = 0;
    
    // 动态规划转移
    for (int day = 1; day <= n; day++) {
        // 重置