笔试时间：2025年9月5日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：城市公路维修时间

题目描述： 城市公路某些路段路面质量下降，多多需要对这些路段进行维修。多多可进行工作的时间为H。同时有交通管理系统会根据不同因素发出拥堵预警。多多的维修应当在路况不繁忙的时候进行，需要注意预警时段可能存在重叠。请你帮助多多计算可以进行公路维修的时间共有多少。

输入描述

第一行为一个整数T，表示共有T个测试数据，且1≤T≤100

每组测试数据：

第一行为一个整数H，表示多多可进行维修的工作总时长，且1≤H≤10^9

第二行为一个整数N，表示预警时段的个数，且0≤N≤10^5

接下来的N行，每行输入两个整数li, ri，表示区间[li,ri]被预警将有拥堵发生，且1≤li≤ri≤H

输出描述

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

样例输入

1

10

2

5 10

5 5

样例输出

4

参考题解

把所有拥堵预警区间做并集，求出被占用的总时长，再用可工作总时长H减去它即可。先按起点对所有区间排序，然后扫描合并重叠区间，最后计算预警总时长。

C++：

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

void solve() {
    int T;
    cin >> T;
    while (T--) {
        int H, N;
        cin >> H >> N;
        vector<pair<int, int>> intervals(N);
        for (int i = 0; i < N; i++) {
            cin >> intervals[i].first >> intervals[i].second;
        }
        
        if (intervals.empty()) {
            cout << H << endl;
            continue;
        }
        
        sort(intervals.begin(), intervals.end());
        
        vector<pair<int, int>> merged;
        int l = intervals[0].first, r = intervals[0].second;
        
        for (int i = 1; i < N; i++) {
            int x = intervals[i].first, y = intervals[i].second;
            if (x <= r) {
                r = max(r, y);
            } else {
                merged.push_back({l, r});
                l = x;
                r = y;
            }
        }
        merged.push_back({l, r});
        
        long long blocked = 0;
        for (auto& p : merged) {
            blocked += p.second - p.first + 1;
        }
        
        cout << H - blocked << endl;
    }
}

int main() {
    solve();
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int H = sc.nextInt();
            int N = sc.nextInt();
            
            List<int[]> intervals = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                intervals.add(new int[]{l, r});
            }
            
            if (intervals.isEmpty()) {
                System.out.println(H);
                continue;
            }
            
            intervals.sort((a, b) -> a[0] - b[0]);
            
            List<int[]> merged = new ArrayList<>();
            int l = intervals.get(0)[0], r = intervals.get(0)[1];
            
            for (int i = 1; i < N; i++) {
                int x = intervals.get(i)[0];
                int y = intervals.get(i)[1];
                if (x <= r) {
                    r = Math.max(r, y);
                } else {
                    merged.add(new int[]{l, r});
                    l = x;
                    r = y;
                }
            }
            merged.add(new int[]{l, r});
            
            long blocked = 0;
            for (int[] p : merged) {
                blocked += p[1] - p[0] + 1;
            }
            
            System.out.println(H - blocked);
        }
    }
    
    public static void main(String[] args) {
        solve();
    }
}

Python：

def solve():
    import sys
    input = sys.stdin.readline
    T = int(input().strip())
    for _ in range(T):
        H = int(input().strip())
        N = int(input().strip())
        intervals = [tuple(map(int, input().split())) for _ in range(N)]
        
        if not intervals:
            print(H)
            continue
        
        # 按起点排序
        intervals.sort()
        
        merged = []
        l, r = intervals[0]
        
        for x, y in intervals[1:]:
            if x <= r:  # 有交集，合并
                r = max(r, y)
            else:  # 无交集，保存
                merged.append((l, r))
                l, r = x, y
        merged.append((l, r))
        
        # 计算预警总时长
        blocked = sum(r - l + 1 for l, r in merged)
        print(H - blocked)

solve()

第二题：魔法森林传送门

题目描述： 在一片神奇的魔法森林中，有n个魔法节点，每个节点都有一个传送门。第i个节点的传送门会把你传送到a[i]号节点。多多每次可以选择坐传送门从i节点传送到a[i]节点，或者选择步行到相邻的节点i-1或i+1节点。现在多多从1号节点出发，想知道到达每个节点需要经过的最少步行次数。

输入描述

输入两行，第一行包含一个数字n，表示有n个节点（1≤n≤10^5）

接下来一行n个数字，每个数字a[i]（1≤a[i]≤n），表示第i节点的传送门可以传送到a[i]节点

输出描述

输出一行包含n个数字，第i个数字表示从1号节点到i号节点的最少步行次数。

样例输入

3

1 2 3

样例输出

0 1 2

参考题解

这是一个0-1 BFS问题。传送门不需要步行（代价为0），走到相邻节点需要一步（代价为1）。使用双端队列，代价为0的边用appendleft，代价为1的边用append。

C++：

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> dist(n + 1, 1e9);
    dist[1] = 0;
    deque<int> q;
    q.push_back(1);
    
    while (!q.empty()) {
        int x = q.front();
        q.pop_front();
        
        // 传送门（权重0）
        int y = a[x];
        if (dist[y] > dist[x]) {
            dist[y] = dist[x];
            q.push_front(y);
        }
        
        // 步行到相邻节点（权重1）
        if (x > 1 && dist[x - 1] > dist[x] + 1) {
            dist[x - 1] = dist[x] + 1;
            q.push