✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：音乐谱曲的回响效果

1️⃣：解析输入字符串，识别小节结构和内容

2️⃣：根据回响规则，对每个小节生成对应的回响效果

3️⃣：处理长度限制和下划线填充

难度：中等

这道题目要求根据特定规则为音乐片段生成回响效果。关键在于理解回响生成的规则：在每个小节前添加 p 个下划线，然后截取与原小节相同长度的部分。通过对字符串的处理和操作，可以高效地生成符合规则的回响效果。

题目二：网格信息矩阵变换

1️⃣：理解反对角线的定义和反转操作

2️⃣：遍历所有可能的反对角线

3️⃣：收集并反转元素，然后重新填回原位置

难度：中等

这道题目考察对二维矩阵的操作和变换。通过识别并收集每条反对角线（满足 j-i 为常数的元素）上的元素，将它们反转后重新填回原位置，可以实现特定的矩阵变换效果。该解法具有 O(n×m) 的时间复杂度。

题目三：景区观光路线规划

1️⃣：使用并查集维护景点连通性

2️⃣：按吸引力指数从小到大处理所有景点

3️⃣：统计精品路线的数量，包括单点路径和双端点路径

难度：中等偏难

这道题目需要理解"精品路线"的定义，并找到一种高效的方法来统计符合条件的路径数量。通过使用并查集按吸引力指数从小到大处理景点，可以有效地处理连通性并计算路径数量。该解法的时间复杂度为 O(n log n)。

01. 音乐谱曲的回响效果

问题描述

小毛是一位音乐制作人，他正在研究一种名为"回响"的音乐效果。在他的音乐编辑软件中，音乐片段用字符串表示，仅由小写字母和连接线'-'构成。每个音乐片段用竖线'|'来划分小节，例如，|do-do-re|re---|表示两个小节，第一个小节长度为8字符（"do-do-re"），第二个小节长度为5字符（"re---"）。

小毛希望为原始音乐创建回响效果。回响的规则如下：

• 回响与原音乐具有相同数量的小节，且每个小节长度与原音乐对应小节相同
• 回响比原音乐晚 个长度单位出现
• 回响尚未出现的部分用下划线'_'填充
• 如果回响超出小节范围，则直接截断
• 回响的生成方法是：先在每个小节前面添加 个下划线，然后截取与原小节相同长度的部分

小毛现在需要你根据给定的原始音乐和参数 ，自动生成相应的回响效果。

输入格式

第一行输入两个整数 、（；），分别表示原始音乐字符串的总长度（包括 | 在内）和回响延迟的长度。

接下来若干行，一共输入 个字符，表示原始音乐字符串。

保证每行的首末均为竖线（|），每个小节的长度至少为 1，小节中的字符仅为小写字母和连接线（-）。

输出格式

根据输入，输出若干行，表示生成的回响音乐字符串。

样例输入

16 2
|do-do-re|re---|

15 0
|ciallo|
|-|
|--|

7 2
|-|
|--|

16 2
|do-do-re|mi---|

样例输出

|__do-do-|__re-|

|ciallo|
|-|
|--|

|_|
|__|

|__do-do-|__mi-|

样例 解释说明

样例1	第一个小节的回响：原小节"do-do-re"前添加2个下划线变为"__do-do-re"，截取8个字符得到"__do-do-"；第二个小节的回响：原小节"re---"前添加2个下划线变为"__re---"，截取5个字符得到"__re-"。
样例2	当延迟p=0时，回响与原音乐完全相同。
样例3	小节长度较短的情况下，回响可能只包含下划线。第一个小节长1，添加2个下划线后截取1个，变为"_"；第二个小节长2，添加2个下划线后截取2个，变为"__"。
样例4	与样例1类似，但第二个小节的原内容为"mi---"。

数据范围

• 
• 
• 保证每个小节长度至少为1

题解

这道题考查的是字符串处理，特别是如何根据规则生成新的字符串。

解题的关键在于理解"回响"的生成规则：对于每个小节，我们需要在前面添加 个下划线，然后截取与原小节相同长度的部分作为回响。

解题步骤如下：

1. 首先，我们需要读取整个输入，将其按小节分割。小节的边界由'|'标记。
2. 对于每个小节，我们提取出小节内容（不含边界的'|'）。
3. 计算小节的长度 。
4. 创建回响：添加 个下划线（因为即使 很大，超过小节长度的部分也会被截断）。
5. 然后添加原小节内容，并截取前 个字符作为最终的回响。
6. 在回响前后添加'|'并输出。

时间复杂度分析：我们只需要遍历一次输入字符串，对每个字符进行常数时间的处理，所以时间复杂度是 ，其中 是输入字符串的长度。空间复杂度也是 ，我们需要存储输入字符串和生成的回响字符串。

注意：虽然 可能高达 ，但实际添加的下划线数量不会超过小节长度，所以不会导致空间问题。

参考代码

• Python

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

# 读取输入
n, p = map(int, input().split())
sections = []
total_len = 0

# 读取所有行，累计长度直到达到n
while total_len < n:
    line = input()
    if line:
        sections.append(line)
        total_len += len(line)

# 处理每个小节生成回响
for i, section in enumerate(sections):
    # 提取小节内容（不含边界的'|'）
    section_len = len(section) - 2  # 减去两端的'|'
    section_content = section[1:-1]
    
    # 创建回响：添加下划线并截取合适长度
    underscore_count = min(p, section_len)  # 添加的下划线数量
    echo = '_' * underscore_count + section_content
    echo = echo[:section_len]  # 截取与原小节相同长度
    
    # 输出带边界的回响
    print(f"|{echo}|", end="")
    if i < len(sections) - 1:
        print()  # 除最后一个小节外，每个小节后换行

• Cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    // 加速输入
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    ll n, p;
    cin >> n >> p;
    
    string line;
    vector<string> segs;  // 存储所有小节
    ll total = 0;
    
    // 读取每一行，累计长度直到达到n
    while (total < n && getline(cin, line)) {
        if (line.empty()) continue;  // 跳过空行
        segs.push_back(line);
        total += line.size();
    }
    
    // 处理每个小节
    for (size_t i = 0; i < segs.size(); i++) {
        string &s = segs[i];
        int len = s.size() - 2;  // 小节长度（不含两端的'|'）
        string content = s.substr(1, len);  // 小节内容
        
        // 创建回响
        ll ucount = min<ll>(p, len);  // 添加的下划线数
        string echo = string(ucount, '_') + content;
        echo = echo.substr(0, len);  // 截取与原小节相同长度
        
        // 输出带边界的回响
        cout << '|' << echo << '|';
        if (i + 1 < segs.size()) cout << '\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));
        String[] firstLine = br.readLine().split(" ");
        
        // 读取输入
        long n = Long.parseLong(firstLine[0]);
        long p = Long.parseLong(firstLine[1]);
        
        List<String> segs = new ArrayList<>();
        long total = 0;
        
        // 读取每一行，累计长度直到达到n
        String line;
        while (total < n && (line = br.readLine()) != null) {
            if (line.isEmpty()) continue;
            segs.add(line);
            total += line.length();
        }
        
        // 处理每个小节
        for (int i = 0; i < segs.size(); i++) {
            String s = segs.get(i);
            int len = s.length() - 2;  // 小节长度（不含两端的'|'）
            String content = s.substring(1, len + 1);  // 小节内容
            
            // 创建回响
            int ucount = (int)Math.min(p, len);  // 添加的下划线数
            StringBuilder echo = new StringBuilder();
            for (int j = 0; j < ucount; j++) {
                echo.append('_');
            }
            echo.append(content);
            
            // 截取与原小节相同长度
            if (echo.length() > len) {
                echo = new StringBuilder(echo.substring(0, len));
            }
            
            // 输出带边界的回响
            System.out.print("|" + echo + "|");
            if (i < segs.size() - 1) {
                System.out.println();  // 除最后一个小节外，每个小节后换行
            }
        }
    }
}

02. 网格信息矩阵变换

问题描述

小基正在设计一个数据可视化系统，需要对信息矩阵进行特殊的变换处理。他定义了一种"反对角线反转"操作：对于一个 的网格矩阵，将每条反对角线（即满足 为常数的所有单元格）上的元素按照从右上到左下的顺序反转排列。

更具体地说，对于网格中所有满足 的单元格（其中 是一个常数），收集这些单元格上的所有元素，然后将它们反转后重新填回原来的位置。这个操作需要对所有可能的 值（从 到 ）都执行一次。

小基想知道，对于给定的初始网格矩阵，执行"反对角线反转"操作后的结果是什么。

输入格式

第一行输入两个正整数 、（），表示网格的行数和列数。

接下来 行，每行输入 个正整数 （），表示网格中第 行第 列的元素值。

输出格式

输出 行，每行 个整数，表示执行"反对角线反转"操作后的网格矩阵。

样例输入

2 3
1 3 2
4 6 5

样例输出

6 5 2
4 1 3

样例 解释说明

样例1	原矩阵为： 1 3 2 4 6 5 反对角线包括：(0,0)-(1,-1)即只有元素1；(0,1)-(1,0)为元素3和4，反转后变为4和3；(0,2)-(1,1)为元素2和6，反转后变为6和2；(2,1)即只有元素5。所以变换后的矩阵为： 6 5 2 4 1 3

数据范围

• 
• 

题解

这道题要求我们实现一种特殊的矩阵变换操作，即"反对角线反转"。理解这个操作是解题的关键。

在一个矩阵中，反对角线是指那些满足 的单元格集合，其中 是一个常数。例如，当 时，反对角线包括 (0,1), (1,2), (2,3) 等位置的元素。题目要求我们对每条反对角线上的元素进行反转，即将它们按照从右上到左下的顺序倒过来排列。

解题思路如下：

1. 遍历所有可能的 值，即从 到 。
2. 对于每个 ，收集满足 的所有单元格位置和对应的元素值。
3. 将收集到的元素反转排序。
4. 将反转后的元素重新填回对应的位置。

时间复杂度分析：我们需要遍历矩阵中的每个元素一次，对于每条反对角线，我们需要 的时间来收集和反转元素。总共有 条反对角线，因此总时间复杂度为 。

空间复杂度：我们需要额外的空间来存储结果矩阵和临时收集的元素，因此空间复杂度为 。

参考代码

• Python

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

# 读取输入
n, m = map(int, input().split())
grid = []
for _ in range(n):
    row = list(map(int, input().split()))
    grid.append(row)

# 初始化结果矩阵
result = [[0 for _ in range(m)] for _ in range(n)]

# 对每条反对角线进行处理
for k in range(-(n-1), m):
    # 收集当前反对角线上的元素和位置
    diag = []
    pos = []
    
    for i in range(n):
        j = i + k
        if 0 <= j < m:
            diag.append(grid[i][j])
            pos.append((i, j))
    
    # 反转元素
    diag.reverse()
    
    # 将反转后的元素填回原位置
    for idx, (i, j) in enumerate(pos):
        result[i][j] = diag[idx]

# 输出结果
for row in result:
    print(*row)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 读取输入矩阵
    vector<vector<long long>> grid(n, vector<long long>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    // 初始化结果矩阵
    vector<vector<long long>>