✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

滴滴-2026.03.22

题目一：小基 的中转出行计划

这题核心是把“取消哪些班次”压缩成前缀删除。第一段删掉前 班后，小基 的出发时刻就被唯一确定；第二段再用二分找到最早赶得上的班次，继续跳过剩余被取消的车即可。最容易漏掉的是：只要存在一种分配方式能让整段中转断掉，答案就不是某个时间，而是直接输出 。

难度：Low

题目二：小毛的走廊铺设概率

表面是概率题，实质上要先把“选中某条线段”的贡献拆成基础不选概率和一个额外权值，然后转成带权区间恰好覆盖 DP。真正的难点在于 的必选线段，它们既可能直接把答案卡成 ，也会把一批普通线段整段排除掉。把这部分先清干净，后面的转移就很顺了。

难度：Mid

1. 小基 的中转出行计划

问题描述

小基 需要从站点 出发，先到中转站 ，再从 前往终点站 。

已知：

• 从 到 一共有 班接驳车，第 班的发车时刻为 。
• 从 到 一共有 班接驳车，第 班的发车时刻为 。
• 任意一班 的车程都固定为 。
• 任意一班 的车程都固定为 。

如果 小基 乘坐某班发车时刻为 的 接驳车，那么她会在 时刻到达 ；第二段同理。

现在你可以取消恰好 班接驳车，并且希望让 小基 尽可能晚到达终点站 。

如果存在一种取消方案，能够让她根本无法从 到达 ，请直接输出 。

输入格式

第一行输入五个整数 。

第二行输入 个整数 ，表示第一段接驳车的发车时刻。

第三行输入 个整数 ，表示第二段接驳车的发车时刻。

输出格式

输出一行一个整数，表示在最优取消方案下，小基 最晚到达终点站 的时刻；若可以让她无法到达，则输出 。

样例输入

3 3 1 2 2
1 5 7
2 6 8

3 3 1 2 3
1 5 7
2 6 8

样例输出

10

-1

数据范围

• 
• 
• 
• 
• 

样例	解释说明
样例 1	无论把这 次取消怎么分配，小基 最终最晚都只能在时刻 抵达终点。例如取消第一段最早的 班、第二段最早的 班后，她会在时刻 到达中转站，再乘坐第二段发车时刻为 的车，于时刻 到达。
样例 2	可以直接让答案变成 。例如取消第一段最早的 班，再取消第二段的前 班。这样 小基 到达中转站后，剩余的第二段车次已经全部赶不上了，因此无法到达终点。

题解

这题真正需要想清楚的，不是“删哪几班更花哨”，而是：

如果第一段删掉了 班，那么被删掉的一定是最早的那 班。

原因很直接。小基 总会乘坐当前还能搭上的最早一班车。想把她往后拖，删掉后面的车没有意义，只有把前面的车删掉，才会真的把她逼到更晚的那一班。

于是第一段的取消方案可以直接压缩成一个整数：

• 删掉前 班 的接驳车。
• 那么 小基 第一段一定会乘坐 这一班（这里按 下标理解）。

接下来分情况讨论。

一、固定第一段删了多少班

假设第一段删了 班，那么：

• 小基 会在时刻 到达中转站 。
• 还剩下 次取消，要放在第二段。

设第二段里第一班来得及赶上的车次下标为 pos，也就是满足：

并且 pos 最小。

这可以直接用二分查找，也就是 lower_bound 找出来。

既然目标是让她尽量晚到，那么在第二段里也应该优先删掉她本来最早能坐上的那些车。因此：

• 先跳过 pos 之前所有本来就赶不上的车；
• 再额外删掉从 pos 开始的前 班可用车；
• 她最终会被迫乘坐下标 pos + (k - i) 的那一班。

如果这个下标已经越界，说明存在一种取消方案能让她第二段完全无车可坐，那么答案立刻就是 。

二、为什么只要枚举

第一段一共删多少班，取值范围就是 。

对于每个 ：

1. 第一段的选择已经唯一确定。
2. 第二段最优的拖延方式也唯一确定，就是删掉最早还能赶上的那些车。

因此只要把所有 都试一遍，就不会漏掉最优方案。

三、边界怎么处理

有两种特别容易漏掉的情况。

第一种是 或 。

• 如果 ，那就可以把第一段全删掉。
• 如果 ，那就可以把第二段全删掉。

这两种都能直接让 小基 无法到达终点，所以答案一定是 。

第二种是某个枚举到的 会让第二段下标越界。

这同样说明“存在一种取消方案能断路”，因此也应该立刻输出 ，而不是只跳过这个方案。

四、复杂度分析

设第一段枚举了 种分配方式。

• 每次枚举都只做一次二分查找，复杂度是 。
• 总复杂度就是 。

在本题的数据范围下完全可以通过。

参考代码

• Python

import sys
from bisect import bisect_left

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


def solve():
    n, m, ta, tb, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    # 只要能把某一段全部删光，就可以直接让整趟行程失败。
    if k >= n or k >= m:
        print(-1)
        return

    ans = 0

    # i 表示第一段删掉了前 i 班车。
    for i in range(k + 1):
        arr = a[i] + ta

        # 找到第二段中第一班来得及赶上的车。
        pos = bisect_left(b, arr)

        # 第二段还要再删掉 k-i 班可用车。
        pos += k - i

        # 只要存在一种方案让第二段无车可坐，答案就必须是 -1。
        if pos >= m:
            print(-1)
            return

        ans = max(ans, b[pos] + tb)

    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

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

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    int64 ta, tb;
    cin >> n >> m >> ta >> tb >> k;

    vector<int64> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }

    // 某一段可以被全部取消时，整趟路线必定断开。
    if (k >= n || k >= m) {
        cout << -1 << '\n';
        return 0;
    }

    int64 ans = 0;

    for (int i = 0; i <= k; ++i) {
        int64 arr = a[i] + ta;

        // 找第二段里第一班还能赶上的车。
        int pos = lower_bound(b.begin(), b.end(), arr) - b.begin();

        // 再跳过第二段中被取消的 k-i 班可用车。
        pos += k - i;

        // 只要这次分配方式能让人断路，最终答案就是 -1。
        if (pos >= m) {
            cout << -1 << '\n';
            return 0;
        }

        ans = max(ans, b[pos] + tb);
    }

    cout << ans << '\n';
    return 0;
}

• Java

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

public class Main {
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            while ((c = read()) <= ' ') {
                if (c == -1) {
                    return -1;
                }
            }
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }
    }

    static int lowerBound(long[] arr, long target) {
        int l = 0;
        int r = arr.length;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();

        int n = (int) fs.nextLong();
        int m = (int) fs.nextLong();
        long ta = fs.nextLong();
        long tb = fs.nextLong();
        int k = (int) fs.nextLong();

        long[] a = new long[n];
        long[] b = new long[m];
        for (int i = 0; i < n; i++) {
            a[i] = fs.nextLong();
        }
        for (int i = 0; i < m; i++) {
            b[i] = fs.nextLong();
        }

        // 能删光其中任意一段，就一定可以让最终路线失败。
        if (k >= n || k >= m) {
            System.out.println(-1);
            return;
        }

        long ans = 0;

        for (int i = 0; i <= k; i++) {
            long arr = a[i] + ta;

            // 找第二段第一班还赶得上的车。
            int pos = lowerBound(b, arr);

            // 再跳过第二段中被额外取消的车次。
            pos += k - i;

            // 一旦存在一种断路方案，就应该直接输出 -1。
            if (pos >= m) {
                System.out.println(-1);
                return;
            }

            ans = Math.max(ans, b[pos] + tb);
        }

        System.out.println(ans);
    }
}

2. 小毛的走廊铺设概率

问题描述

小毛维护着一条长度为 的走廊。走廊被分成了从左到右编号为 到 的 个格子。

现在一共有 段地毯候选方案。第 段地毯由四个整数 描述，含义如下：

• 如果这段地毯被铺上，它会覆盖所有编号在 之间的格子。
• 这段地毯会以 的概率被铺上。
• 每段地毯是否被铺上，彼此相互独立。

请计算“每一个格子都被恰好一段地毯覆盖”的概率。

答案需要对模数 取模输出。若该概率写成最简分数 ，则输出：

其中 表示 在模 意义下的乘法逆元。

输入格式

第一行输入两个整数 ，分别表示候选地毯数量和走廊长度。

第二行输入 个整数，表示所有 。

第三行输入 个整数，表示所有 。

第四行输入 个整数，表示所有 。

第五行输入 个整数，表示所有 。

输出格式

输出一行一个整数，表示“每个格子都被恰好一段地毯覆盖”的概率对 取模后的结果。

样例输入

3 3
1 3 1
2 3 3
1 1 2
3 2 3

2 3
1 2
2 3
1 1
2 2

8 5
1 1 1 5 4 4 3 1
3 5 4 5 5 5 3 2
1 1 4 1 1 2 2 1
2 6 5 7 2 5 7 3

样例输出

610038216

0

94391813

数据范围

• 
• 
• 

样例	解释