✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

拼多多-2025.11.09

题目一：字符串的有效配对

1️⃣：提取非通配符字符的位置，统计纯通配符段的最大长度

2️⃣：在非通配符字符上使用栈进行括号匹配

3️⃣：每次匹配成功后向左右扩展包含相邻的通配符

难度：中等

题目二：图书馆的借阅统计

1️⃣：使用差分数组统计每个位置被查询覆盖的次数

2️⃣：将书籍价值数组和位置频次数组分别排序

3️⃣：利用排序不等式计算最大点积和

难度：中等

题目三：物流配送的路线规划

1️⃣：定义 dp[i] 表示完成前 i 个包裹的最小成本

2️⃣：枚举每个起点，尝试装载连续的若干包裹

3️⃣：根据累计重量选择小型车或大型车，更新状态

难度：中等

题目四：网络集群的价值最大化

1️⃣：使用 BFS 找出所有连通块并计算每个连通块的直径

2️⃣：将所有连通块的直径按降序排序

3️⃣：按照最优合并策略使用数学公式计算最大总价值

难度：中等偏难

1. 字符串的有效配对

问题描述

K 小姐正在开发一个文本编辑器的括号匹配功能。编辑器中的文本由左括号 (、右括号 ) 和通配符 * 组成。K 小姐需要找出文本中最长的连续片段，使得在忽略所有通配符 * 之后，这个片段中的括号能够完美配对。

所谓完美配对需要满足以下条件：

1. 每个左括号 ( 都能找到一个对应的右括号 )

2. 括号的嵌套顺序正确：任何右括号都不能出现在它对应的左括号之前

通配符 * 在检查时会被完全忽略，它们不参与配对，但会计入最终的长度。

输入格式

第一行输入一个整数 ，表示测试用例的组数，其中 。

接下来 组数据，每组测试用例包含两行。

第一行输入一个整数 ，表示字符串的长度，其中 。

第二行输入一个长度为 的字符串，字符串仅由 (、) 和 * 组成。

输出格式

输出包含 行。

每行输出一个整数，表示满足要求的最长连续子串的长度。

样例输入

3
8
*(*(**))
4
(()*
8
*(()(*)*

2
4
****
4
)))(

样例输出

8
3
6

4
0

数据范围

• 

• 

样例	解释说明
样例1-1	整个字符串 *(*(**)) 长度为 8，去掉 * 后为 (()))，其中前 4 个字符 (()) 可以完美配对，因此可以从头到尾取整个字符串，长度为 8
样例1-2	字符串 (()* 中，去掉 * 后为 (() 只有一对括号能配对，对应原串中的 (() 或包含 * 的片段，最长为 3
样例1-3	字符串 *(()(*)* 中，取子串 (()(*)（长度 6）去掉 * 后为 (()) 完美配对
样例2-1	字符串 **** 全是通配符，本身就是一个有效片段，长度为 4
样例2-2	字符串 )))( 去掉 * 后仍无法配对，最长有效长度为 0

题解

这道题的关键在于理解通配符 * 的作用：它们在判断括号配对时会被忽略，但在计算长度时需要计入。

基本思路分为两个步骤：

第一步：处理纯通配符段

首先遍历字符串，如果存在连续的 * 字符，这些段本身就是有效的（因为去掉 * 后是空串，自然满足配对条件）。记录所有连续 * 段的最大长度作为候选答案。

第二步：处理包含括号的情况

核心思想是：先提取出所有非 * 字符的位置，然后在这些位置上做经典的"最长有效括号"匹配，找到一段能够配对的括号序列后，再向左右扩展，把相邻的 * 字符都包含进来。

具体做法：

1. 建立一个位置数组 p[]，记录所有非 * 字符在原串中的下标。

2. 使用栈来处理括号配对：

   • 遇到 ( 就把它的位置压入栈
   • 遇到 ) 时尝试出栈配对
   • 如果栈为空说明这个 ) 无法配对，记录它的位置为最后一个无效位置
   • 每次成功配对后，计算从上一个无效位置到当前位置的区间长度

3. 对于每个成功配对的区间，向左右扩展：

   • 向左扩展到前一个非 * 字符之后
   • 向右扩展到后一个非 * 字符之前
   • 这样就把所有可以包含的 * 都计入了长度

时间复杂度分析：每个字符最多被访问常数次，整体时间复杂度为 ，对于 的数据范围完全可以接受。

参考代码

• Python

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

T = int(input())
for _ in range(T):
    n = int(input())
    s = input()
    
    pos = []  # 存储非*字符的位置
    res = 0
    
    # 统计纯*段的最大长度
    last = -1
    for i in range(n):
        if s[i] != '*':
            res = max(res, i - last - 1)
            pos.append(i)
            last = i
    res = max(res, n - last - 1)
    
    # 在非*字符上做最长有效括号匹配
    stk = []  # 栈存储位置索引
    inv = -1  # 最后一个无效右括号的位置
    m = len(pos)
    
    for i in range(m):
        if s[pos[i]] == '(':
            stk.append(i)
        else:
            if stk:
                stk.pop()
                # 计算当前有效区间的起点
                start = inv + 1 if not stk else stk[-1] + 1
                # 向左右扩展包含所有*
                left = 0 if start == 0 else pos[start - 1] + 1
                right = n - 1 if i + 1 == m else pos[i + 1] - 1
                res = max(res, right - left + 1)
            else:
                inv = i
    
    print(res)

• Cpp

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    while(T--){
        int n;
        string s;
        cin >> n >> s;
        
        vector<int> pos;  // 非*字符位置数组
        long long res = 0;
        
        // 先计算纯*段最大长度
        int pre = -1;
        for(int i = 0; i < n; i++){
            if(s[i] != '*'){
                res = max(res, (long long)(i - pre - 1));
                pos.push_back(i);
                pre = i;
            }
        }
        res = max(res, (long long)(n - pre - 1));
        
        // 在pos数组上做括号匹配
        vector<int> stk;
        int inv = -1;  // 最后无效位置
        int m = pos.size();
        
        for(int i = 0; i < m; i++){
            if(s[pos[i]] == '('){
                stk.push_back(i);
            } else {
                if(!stk.empty()){
                    stk.pop_back();
                    // 当前有效区间起点
                    int st = stk.empty() ? inv + 1 : stk.back() + 1;
                    // 向左右扩展
                    int L = (st > 0) ? pos[st - 1] + 1 : 0;
                    int R = (i + 1 < m) ? pos[i + 1] - 1 : n - 1;
                    res = max(res, (long long)(R - L + 1));
                } else {
                    inv = i;
                }
            }
        }
        
        cout << res << "\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 T = Integer.parseInt(br.readLine());
        
        while(T-- > 0){
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            
            List<Integer> pos = new ArrayList<>();  // 非*字符位置
            long res = 0;
            
            // 统计纯*段长度
            int prev = -1;
            for(int i = 0; i < n; i++){
                if(s.charAt(i) != '*'){
                    res = Math.max(res, i - prev - 1);
                    pos.add(i);
                    prev = i;
                }
            }
            res = Math.max(res, n - prev - 1);
            
            // 括号匹配
            Stack<Integer> stk = new Stack<>();
            int invPos = -1;  // 无效位置
            int m = pos.size();
            
            for(int i = 0; i < m; i++){
                if(s.charAt(pos.get(i)) == '('){
                    stk.push(i);
                } else {
                    if(!stk.isEmpty()){
                        stk.pop();
                        // 有效区间起点
                        int start = stk.isEmpty() ? invPos + 1 : stk.peek() + 1;
                        // 扩展边界
                        int leftBd = (start > 0) ? pos.get(start - 1) + 1 : 0;
                        int rightBd = (i + 1 < m) ? pos.get(i + 1) - 1 : n - 1;
                        res = Math.max(res, rightBd - leftBd + 1);
                    } else {
                        invPos = i;
                    }
                }
            }
            
            System.out.println(res);
        }
    }
}

2. 图书馆的借阅统计

问题描述

小基 负责管理一座大型图书馆。图书馆有 个书架，每个书架上都有一本珍贵的藏书。现在图书馆收到了 份读者的借阅申请，每份申请要求借阅某个连续区间 内所有书架上的书籍。

小基 发现，如果能够重新安排这 本书在书架上的摆放顺序，就可以让所有借阅申请的总满意度最大化。每本书都有一个价值分数，借阅一本书会获得相应的价值分数。

你的任务是帮助 小基 找到最佳的书籍摆放方案，使得所有借阅申请的总价值分数达到最大。

输入格式

第一行输入一个整数 ，表示书架的数量。

第二行输入一个整数 ，表示借阅申请的数量。

第三行输入 个整数 ，表示每本书的价值分数。

接下来 行，每行输入两个整数 和 ，表示一份借阅申请的区间，其中 。

输出格式

输出一个整数，表示最优摆放方案下所有借阅申请的总价值分数。

样例输入

3
2
1 2 3
1 2
1 3

样例输出

11

数据范围

• 

• 

• 每本书的价值分数的绝对值不超过

• 

样例	解释说明
样例1	有 3 个书架和 2 份借阅申请。第一份申请借阅区间 ，第二份申请借阅区间 。位置 1 被借阅 2 次，位置 2 被借阅 2 次，位置 3 被借阅 1 次。最优方案是将价值为 3 的书放在位置 1 或 2（被借阅 2 次），价值为 2 的书放在另一个被借阅 2 次的位置，价值为 1 的书放在位置 3（被借阅 1 次）。总价值为

题解

这道题的关键观察是：无论如何摆放书籍，每个位置被借阅的次数是固定的，只取决于有多少个区间覆盖了这个位置。

因此问题转化为：给定每个位置的被借阅次数和每本书的价值，如何分配才能让总和最大？

答案很简单：把价值最大的书放在被借阅次数最多的位置上。这是一个经典的"排序不等式"问题。

具体步骤：

1. 统计每个位置的被借阅次数：对于每个查询区间 ，区间内的每个位置都被借阅一次。可以使用差分数组快速统计：

   • 对于区间 ，在差分数组的 位置加 1，在 位置减 1
   • 然后对差分数组做前缀和，就得到了每个位置的实际被借阅次数

2. 对两个数组排序：

   • 将书的价值数组从小到大排序
   • 将位置的被借阅次数数组从小到大排序

3. 计算点积：将价值最小的书分配给被借阅次数最少的位置，价值最大的书分配给被借阅次数最多的位置，累加所有的 价值 × 次数 即为答案。

为什么这样是最优的？根据排序不等式（排序后同序相乘和最大），当两个序列都按升序（或都按降序）排列后对应相乘，得到的和是最大的。

时间复杂度：统计频次是 ，排序是 ，总体复杂度 ，对于 完全可以接受。

参考代码

• Python

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

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

# 差分数组统计每个位置的频次
diff = [0] * (n + 1)
for _ in range(q):
    l, r = map(int, input().split())
    diff[l - 1] += 1
    if r < n:
        diff[r] -= 1

# 前缀和得到实际频次
freq = []
cur = 0
for i in range(n):
    cur += diff[i]
    freq.append(cur)

# 排序后计算点积
a.sort()
freq.sort()

ans = sum(a[i] * freq[i] for i in range(n))
print(ans)

• Cpp

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    
    vector<long long> val(n);
    for(int i = 0; i < n; i++){
        cin >> val[i];
    }
    
    // 差分数组
    vector<long long> diff(n + 1, 0);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        diff[l - 1]++;
        if(r < n) diff[r]--;
    }
    
    // 计算每个位置的频次
    vector<long long> freq(n);
    long long sum = 0;
    for(int i = 0; i < n; i++){
        sum += diff[i];
        freq[i] = sum;
    }
    
    // 排序
    sort(val.begin(), val.end());
    sort(freq.begin(), freq.end());
    
    // 计算答案
    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans += val[i] * freq[i];
    }
    
    cout << ans << endl;
    
    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 n = Integer.parseInt(br.readLine());
        int q = Integer.parseInt(br.readLine());
        
        long[] values = new long[n];
        String[] parts = br.readLine().split(" ");
        for(int