✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

拼多多

题目一：小兰的学习时间规划

1️⃣：读取所有干扰区间，按左端点排序进行合并

2️⃣：线性扫描合并重叠或相邻区间，累加合并后的总长度

3️⃣：用总时间减去被干扰覆盖的时间得到答案

难度：中等

这道题目是经典的区间合并问题，关键在于理解如何处理重叠区间和相邻区间。通过排序和线性扫描，可以在 O(N log N) 时间内高效解决。注意处理闭区间的边界条件和使用 long long 避免溢出。

题目二：小毛的地铁导航系统

1️⃣：建模为0-1权重的有向图，快速通道权重0，步行权重1

2️⃣：使用0-1 BFS算法，双端队列维护距离单调性

3️⃣：权重0的边加入队首，权重1的边加入队尾

难度：中等

这道题目巧妙地将最短路问题转化为0-1 BFS。由于边权只有0和1，使用双端队列比传统Dijkstra更高效。算法的正确性依赖于队列中距离值的单调不减性质，时间复杂度为 O(n)。

题目三：小基的花园设计方案

1️⃣：观察矩阵结构，玫瑰花位置是两字符串中'a'位置的笛卡尔积

2️⃣：枚举k的所有约数，对每个约数统计对应长度的连续'a'段数量

3️⃣：扫描字符串找连续'a'段，用L-d+1公式计算子段方案数

难度：中等偏难

这道题目的关键在于理解全为玫瑰花的矩形必须对应连续的'a'行和连续的'a'列。通过约数枚举和连续段统计，将问题转化为高效的数学计算。核心洞察是矩形的行列必须分别来自字符串中的连续'a'段，而不是任意的'a'位置组合。

题目四：小柯的颜色搭配系统

1️⃣：将问题建模为图论连通性问题，颜色为节点

2️⃣：对每个不匹配位置在对应颜色间连边

3️⃣：使用并查集维护连通块，答案为所有连通块大小减一之和

难度：中等偏难

这道题目的精髓在于将序列操作问题转化为图论问题。通过观察操作的本质（颜色合并），可以发现问题等价于求图中各连通块的最小生成树边数。并查集的使用使得算法在 O(n α(n)) 时间内完成，非常高效。

01. 小兰的学习时间规划

问题描述

小兰是一位勤奋的学生，她计划在接下来的 个小时内进行专注学习。但是在这段时间内，会有一些干扰因素影响她的学习效果，比如：室友聚会、在线课程直播、社团活动等。小兰希望避开这些干扰时段来保证学习质量。

需要注意的是，不同的干扰因素可能会有时间重叠。例如，社团活动安排在第 小时，而室友聚会安排在第 小时，那么整个 时段都会受到干扰，小兰都无法安心学习。

请你帮助小兰计算出她总共可以进行有效学习的时间长度。

输入格式

第一行为一个整数 ，表示共有 个测试数据。

每组测试数据：

第一行为一个整数 ，表示小兰计划学习的总时长。

第二行为一个整数 ，表示干扰时段的个数。

接下来 行：

每行输入两个整数 ，表示区间 会有干扰发生。

输出格式

每组数据输出一个结果，每个结果占一行。

样例输入

1
10
2
5 10
5 5

1
3
1
1 3

1
5
2
1 2
4 5

样例输出

4

0

1

样例	解释说明
样例1	小兰只能在 的时间段内进行学习，有效学习时长为 4
样例2	小兰的学习时间内全都有干扰，无法进行有效学习
样例3	小兰只能在第 3 个小时进行学习，有效学习时长为 1

数据范围

题解

这道题的本质是一个经典的区间合并问题。需要计算出所有干扰时段合并后的总长度，然后用总时间减去被干扰的时间就是答案。

解题思路分析：

核心思想：将所有干扰区间合并，计算被覆盖的总时间长度，最后用总时间减去被覆盖的时间。

算法步骤：

1. 读取所有干扰区间
2. 按照左端点对区间进行排序
3. 线性扫描合并重叠或相邻的区间
4. 累加合并后各区间的长度
5. 答案 = - 被干扰覆盖的总长度

合并策略：对于排序后的区间，维护当前合并区间的左右边界。遍历每个新区间时：

• 如果新区间的左端点 ≤ 当前区间的右端点+1，说明可以合并，更新右边界
• 否则说明出现了gap，将当前区间加入答案，开始新的合并区间

实现细节：

• 注意区间是闭区间，相邻区间 和 可以合并成
• 使用long long避免溢出
• 最后别忘了处理最后一个合并区间

时间复杂度：（主要是排序），空间复杂度：。

参考代码

• Python

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

def solve():
    h = int(input())
    n = int(input())
    
    # 读取干扰区间
    segs = []
    for _ in range(n):
        x, y = map(int, input().split())
        segs.append((x, y))
    
    # 按左端点排序
    segs.sort()
    
    # 合并重叠区间并累加长度
    total_blocked = 0
    left, right = -1, -1
    
    for x, y in segs:
        if left == -1:
            # 第一个区间
            left, right = x, y
        elif x <= right + 1:
            # 可以合并，更新右边界
            right = max(right, y)
        else:
            # 不能合并，累加当前区间长度
            total_blocked += right - left + 1
            left, right = x, y
    
    # 处理最后一个区间
    if left != -1:
        total_blocked += right - left + 1
    
    # 计算有效学习时间
    result = max(0, h - total_blocked)
    return result

T = int(input())
for _ in range(T):
    print(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--) {
        long long H;
        int N;
        cin >> H >> N;
        
        // 读取干扰区间
        vector<pair<long long, long long>> segs(N);
        for (int i = 0; i < N; i++) {
            cin >> segs[i].first >> segs[i].second;
        }
        
        // 按左端点排序
        sort(segs.begin(), segs.end());
        
        // 合并重叠区间并累加长度
        long long blocked = 0;
        long long left = -1, right = -1;
        
        for (const auto& seg : segs) {
            long long x = seg.first, y = seg.second;
            
            if (left == -1) {
                // 第一个区间
                left = x;
                right = y;
            } else if (x <= right + 1) {
                // 可以合并，更新右边界
                right = max(right, y);
            } else {
                // 不能合并，累加当前区间长度
                blocked += right - left + 1;
                left = x;
                right = y;
            }
        }
        
        // 处理最后一个区间
        if (left != -1) {
            blocked += right - left + 1;
        }
        
        // 计算有效学习时间
        long long ans = max(0LL, H - blocked);
        cout << ans << "\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));
        
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            long H = Long.parseLong(br.readLine());
            int N = Integer.parseInt(br.readLine());
            
            // 读取干扰区间
            long[][] segs = new long[N][2];
            for (int i = 0; i < N; i++) {
                String[] parts = br.readLine().split(" ");
                segs[i][0] = Long.parseLong(parts[0]);
                segs[i][1] = Long.parseLong(parts[1]);
            }
            
            // 按左端点排序
            Arrays.sort(segs, (a, b) -> Long.compare(a[0], b[0]));
            
            // 合并重叠区间并累加长度
            long blocked = 0;
            long left = -1, right = -1;
            
            for (long[] seg : segs) {
                long x = seg[0], y = seg[1];
                
                if (left == -1) {
                    // 第一个区间
                    left = x;
                    right = y;
                } else if (x <= right + 1) {
                    // 可以合并，更新右边界
                    right = Math.max(right, y);
                } else {
                    // 不能合并，累加当前区间长度
                    blocked += right - left + 1;
                    left = x;
                    right = y;
                }
            }
            
            // 处理最后一个区间
            if (left != -1) {
                blocked += right - left + 1;
            }
            
            // 计算有效学习时间
            long result = Math.max(0, H - blocked);
            System.out.println(result);
        }
    }
}

02. 小毛的地铁导航系统

问题描述

小毛是一名城市规划师，他负责设计一套新的地铁导航系统。这个城市有 个地铁站，编号从 1 到 。每个地铁站 都有一条专门的快速通道，可以免费瞬间到达指定的地铁站 （快速通道不消耗体力）。

除了使用快速通道，乘客还可以选择步行到相邻的地铁站。从地铁站 可以步行到地铁站 或 （如果存在的话），每次步行会消耗 1 点体力。

小毛作为一个提倡节能环保的人，希望乘客能够尽可能少地步行。现在小毛想知道：从 1 号地铁站出发，到达每个地铁站所需要的最少步行次数是多少。

输入格式

输入两行，第一行包含一个数字 ，表示有 个地铁站。

接下来一行 个数字，每个数字 ，表示 号地铁站的快速通道可以到达 号地铁站，注意 可能等于 。

输出格式

输出一行包含 个数字，第 个数字表示从 1 号地铁站到 号地铁站的最少步行次数。

样例输入

3
1 2 3

4
4 2 3 1

样例输出

0 1 2

0 1 1 0

数据范围

题解

这道题本质上是一个带权最短路问题，但权值只有0和1，可以用0-1 BFS高效求解。

问题建模：

• 每个地铁站是一个节点
• 快速通道：从站点 到站点 ，权重为0（不消耗体力）
• 步行：从站点 到站点 或 ，权重为1（消耗1点体力）

算法选择：由于边权只有0和1，使用0-1 BFS比传统的Dijkstra算法更高效。0-1 BFS的核心思想是使用双端队列：

• 权重为0的边：将目标节点加入队列前端
• 权重为1的边：将目标节点加入队列后端

这样保证了队列中的距离值始终是单调不减的，从而保证算法的正确性。

算法流程：

1. 初始化距离数组，设置起点1的距离为0
2. 将起点加入双端队列
3. 从队列中取出节点u，尝试更新其邻居：
   • 快速通道：如果 ，更新并加入队列前端
   • 步行到 和 ：如果距离可以优化，更新并加入队列后端
4. 重复直到队列为空

实现要点：

• 使用deque实现双端队列
• 注意边界检查（ 和 ）
• 距离更新时要检查是否真的能优化

时间复杂度：，因为每个节点最多被处理一次。空间复杂度：。

参考代码

• Python

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

n = int(input())
a = [0] + list(map(int, input().split()))  # 1-indexed

# 初始化距离数组
INF = float('inf')
dist = [INF] * (n + 1)
dist[1] = 0

# 0-1 BFS
dq = deque([1])

while dq:
    u = dq.popleft()
    cur_dist = dist[u]
    
    # 快速通道：权重0
    v = a[u]
    if dist[v] > cur_dist:
        dist[v] = cur_dist
        dq.appendleft(v)
    
    # 步行到u-1：权重1
    if u > 1:
        v = u - 1
        if dist[v] > cur_dist + 1:
            dist[v] = cur_dist + 1
            dq.append(v)
    
    # 步行到u+1：权重1
    if u < n:
        v = u + 1
        if dist[v] > cur_dist + 1:
            dist[v] = cur_dist + 1
            dq.append(v)

# 输出结果
result = []
for i in range(1, n + 1):
    result.append(str(dist[i]))
print(' '.join(result))

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 初始化距离数组
    const int INF = 1e9;
    vector<int> dist(n + 1, INF);
    dist[1] = 0;
    
    // 0-1 BFS
    deque<int> dq;
    dq.push_back(1);
    
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        
        int cur_dist = dist[u];
        
        // 快速通道：权重0
        int v = a[u];
        if (dist[v] > cur_dist) {
            dist[v] = cur_dist;
            dq.push_front(v);
        }
        
        // 步行到u-1：权重1
        if (u > 1) {
            v = u - 1;
            if (dist[v] > cur_dist + 1) {
                dist[v] = cur_dist + 1;
                dq.push_back(v);
            }
        }
        
        // 步行到u+1：权重1
        if (u < n) {
            v = u + 1;
            if (dist[v] > cur_dist + 1) {
                dist[v] = cur_dist + 1;
                dq.push_back(v);
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << " ";
        cout << dist[i];
    }
    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));
        
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(line[i - 1]);
        }
        
        // 初始化距离数组
        final int INF = (int) 1e9;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        
        // 0-1 BFS
        Deque<Integer> dq = new ArrayDeque<>();
        dq.offerLast(1);
        
        while (!dq.isEmpty()) {
            int u = dq.pollFirst();
            int curDist = dist[u];
            
            // 快速通道：权重0
            int v = a[u];
            if (dist[v] > curDist) {
                dist[v] = curDist;
                dq.offerFirst(v);
            }
            
            // 步行到u-1：权重1
            if (u > 1) {
                v = u - 1;
                if (dist[v] > curDist + 1) {
                    dist[v] = curDist + 1;
                    dq.offerLast(v);
                }
            }
            
            // 步行到u+1：权重1
            if (u < n) {
                v = u + 1;
                if (dist[v] > curDist + 1) {
                    di