✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

得物

题目一：小兰的餐厅服务策略

1️⃣：使用动态规划和记忆化搜索计算所有服务方案的评分

2️⃣：将问题转化为合法括号序列，利用卡特兰数的性质

3️⃣：通过状态转移方程 dp[i][d] 计算方案数和总评分

难度：中等

这道题目的核心在于理解栈操作与合法括号序列的对应关系。通过动态规划和记忆化搜索，我们可以有效地计算出所有可能服务策略的总评分，避免了暴力枚举的时间复杂度。

题目二：小毛的密码同步系统

1️⃣：将所有元素先对模数取模，简化问题规模

2️⃣：对其中一个数组排序，使用二分查找快速定位

3️⃣：分情况讨论取模结果，找到最优配对方案

难度：中等

这道题目结合了数学思维和二分查找算法。关键在于理解取模运算的性质，通过合理的搜索策略找到使同步值最小的配对方案。时间复杂度为 O((n+m) log m)，能够处理大规模数据。

题目三：小基的信号传输网络

1️⃣：使用深度优先搜索枚举所有可能的传输路径

2️⃣：利用树状数组(BIT)高效维护逆序对的计算

3️⃣：在DFS过程中实时更新和回溯，优化时间复杂度

难度：中等偏难

这道题目需要理解树上路径的性质和逆序对的定义。通过DFS遍历所有路径，结合树状数组的高效查询和更新操作，我们可以在 O(n² log A) 的时间复杂度内找到逆序对数量最多的路径。

01. 小兰的餐厅服务策略

问题描述

小兰经营着一家高档餐厅，她需要为顾客提供个性化的服务策略。餐厅有 道菜品，第 道菜的制作时间为 分钟。同时，餐厅有一个服务评分体系，当同时为 位顾客服务时，每提供一分钟的服务可以获得 点评分。

小兰的服务流程如下：餐厅有一个待服务队列，小兰可以进行两种操作：

1. 接单操作：当还有菜品未安排时，将下一道菜品加入待服务队列。

2. 完成操作：当待服务队列不为空时，完成队列中最后加入的菜品（后进先出）。设当前队列长度为 ，完成的菜品制作时间为 分钟，则此次操作获得 点评分。

小兰需要进行恰好 次操作（每道菜都要先接单再完成），且每次接单时必须确保还有未安排的菜品，每次完成时必须确保队列非空。

请计算所有可能的服务策略的总评分之和。

输入格式

第一行包含一个正整数 （），表示菜品数量。

第二行包含 个正整数 （），表示每道菜品的制作时间。

第三行包含 个正整数 （），表示不同队列长度对应的评分系数。

输出格式

输出一行一个整数，表示所有不同服务策略的评分之和。

样例输入

2
1 2
2 3

样例输出

14

样例	解释说明
样例1	共有2种服务策略： 策略1：接单→接单→完成→完成，评分为 策略2：接单→完成→接单→完成，评分为 总评分：

数据范围

• 
• 
• 

题解

这道题目本质上是一个关于栈操作和动态规划的问题。我们可以将服务策略看作一个操作序列，其中"接单"相当于压栈操作，"完成"相当于出栈操作。

核心思路是将操作序列等价于长度为 的合法括号序列，其中接单操作对应左括号 (，完成操作对应右括号 )。这样的合法序列总数是第 个卡特兰数 。

我们使用动态规划来解决这个问题。定义状态 ：

• ：已经接单的菜品数量（前 道菜已经进入过队列）
• ：当前队列深度（还有 道菜待完成）

对于每个状态，我们记录：

• cnt[i][d]：从该状态到结束的合法策略数量
• sum[i][d]：从该状态到结束的所有策略总评分之和

状态转移方程：

1. 如果 （还能接单）：转移到状态
2. 如果 （还能完成）：转移到状态 ，并获得额外评分

注意在完成操作时， 是当前栈顶元素的制作时间。

通过记忆化搜索或逆序动态规划，我们可以在 的时间复杂度内解决这个问题。

参考代码

Python

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

def solve():
    n = int(input())
    a = list(map(int, input().split()))  # 读取数组a
    b = [0] + list(map(int, input().split()))  # b数组1-indexed
    
    # 使用记忆化搜索解决问题
    from functools import lru_cache
    
    @lru_cache(None)
    def dp(i, stack_tuple):
        # i: 下一个要处理的元素索引
        # stack_tuple: 当前栈状态(用元组表示)
        
        # 终止条件：所有元素处理完且栈为空
        if i == n and len(stack_tuple) == 0:
            return 1, 0  # (方案数, 总收益)
        
        cnt, total = 0, 0
        
        # 操作1: 压栈 - 如果还有元素未处理
        if i < n:
            new_stack = stack_tuple + (a[i],)  # 将a[i]压入栈
            sub_cnt, sub_sum = dp(i + 1, new_stack)
            cnt += sub_cnt
            total += sub_sum
        
        # 操作2: 弹栈 - 如果栈非空
        if len(stack_tuple) > 0:
            stack_size = len(stack_tuple)  # 当前栈大小
            top_val = stack_tuple[-1]      # 栈顶元素值
            new_stack = stack_tuple[:-1]   # 弹栈后的状态
            
            # 计算本次弹栈获得的收益: b[栈大小] × 栈顶值
            gain = b[stack_size] * top_val
            
            sub_cnt, sub_sum = dp(i, new_stack)
            cnt += sub_cnt
            total += sub_sum + gain * sub_cnt
        
        return cnt, total
    
    _, result = dp(0, ())  # 从状态(0, 空栈)开始
    print(result)

solve()

Cpp

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

int n;
vector<int> a, b;
map<string, pair<ll, ll>> memo;

// 将栈转换为字符串用作缓存键
string stackToStr(const vector<int>& stack) {
    string result = "";
    for (int x : stack) {
        result += to_string(x) + ",";
    }
    return result;
}

pair<ll, ll> dfs(int pos, vector<int> stack) {
    // 创建状态键
    string key = to_string(pos) + "|" + stackToStr(stack);
    if (memo.count(key)) {
        return memo[key];
    }
    
    // 终止条件：所有元素处理完且栈为空
    if (pos == n && stack.empty()) {
        return memo[key] = {1, 0};
    }
    
    ll cnt = 0, sum = 0;
    
    // 操作1: 压栈 - 如果还有元素未处理
    if (pos < n) {
        stack.push_back(a[pos]);  // 将a[pos]压入栈
        auto result = dfs(pos + 1, stack);
        cnt += result.first;
        sum += result.second;
        stack.pop_back();  // 恢复栈状态
    }
    
    // 操作2: 弹栈 - 如果栈非空  
    if (!stack.empty()) {
        int stk_size = stack.size();
        int top_val = stack.back();  // 获取栈顶元素值
        stack.pop_back();  // 弹出栈顶
        
        // 计算收益: b[栈大小] × 栈顶值
        ll gain = 1LL * b[stk_size] * top_val;
        
        auto result = dfs(pos, stack);
        cnt += result.first;
        sum += result.second + gain * result.first;
        
        stack.push_back(top_val);  // 恢复栈状态
    }
    
    return memo[key] = {cnt, sum};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    a.resize(n);
    b.resize(n + 1);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    
    vector<int> empty_stack;
    auto result = dfs(0, empty_stack);
    cout << result.second << "\n";
    
    return 0;
}

Java

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

class Pair {
    long first, second;
    Pair(long f, long s) { first = f; second = s; }
}

public class Main {
    static int n;
    static int[] a, b;
    static Map<String, Pair> memo = new HashMap<>();
    
    // 将栈状态转换为字符串用作缓存键
    static String stackToString(List<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        for (int val : stack) {
            sb.append(val).append(",");
        }
        return sb.toString();
    }
    
    static Pair dfs(int pos, List<Integer> stack) {
        // 创建状态键
        String key = pos + "|" + stackToString(stack);
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        // 终止条件：所有元素处理完且栈为空
        if (pos == n && stack.isEmpty()) {
            Pair result = new Pair(1, 0);
            memo.put(key, result);
            return result;
        }
        
        long cnt = 0, sum = 0;
        
        // 操作1: 压栈 - 如果还有元素未处理
        if (pos < n) {
            stack.add(a[pos]);  // 将a[pos]压入栈
            Pair next = dfs(pos + 1, stack);
            cnt += next.first;
            sum += next.second;
            stack.remove(stack.size() - 1);  // 恢复栈状态
        }
        
        // 操作2: 弹栈 - 如果栈非空
        if (!stack.isEmpty()) {
            int stkSize = stack.size();
            int topVal = stack.get(stkSize - 1);  // 获取栈顶元素值
            stack.remove(stkSize - 1);  // 弹出栈顶
            
            // 计算收益: b[栈大小] × 栈顶值
            long gain = (long) b[stkSize] * topVal;
            
            Pair next = dfs(pos, stack);
            cnt += next.first;
            sum += next.second + gain * next.first;
            
            stack.add(topVal);  // 恢复栈状态
        }
        
        Pair result = new Pair(cnt, sum);
        memo.put(key, result);
        return result;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        a = new int[n];
        b = new int[n + 1];
        
        String[] aStr = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(aStr[i]);
        }
        
        String[] bStr = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            b[i] = Integer.parseInt(bStr[i - 1]);