✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

拼多多-2026.03.29

拼多多-2026.03.29

这套题前两道更偏热身，第三题开始要把排序后的结构看清，第四题是整场分水岭。

第一题顺着过程模拟就能做完。第二题把课程关系看成森林，答案就是最大深度。

第三题的关键是发现一个背包在排序后一定对应连续区间，再把问题拆成两个不重叠区间。

第四题要把每一段接口抽成可以继续往右传递的状态，线性递推维护最优闭环长度。

题目一：小基 的货运巡线

一遍扫描就够。每次先更新载重，再判断当前位置是否安全，同时维护最长连续安全段。

容易漏掉的点是卸货操作。当前载重不够时，结果不是负数，而是直接清成 。

难度：Low

题目二：小基 的排课计划

每门课最多只有一门直接先修课，所以整张图就是若干棵树。

最长先修链给出了学期数下界；按深度分学期又能恰好达到这个下界，所以答案就是最大深度。

难度：Low

题目三：小基 的双背包选品

把价值排好序之后，一个合法背包一定对应一个连续区间。

先用双指针算出每个起点能取多远，再用后缀最优拼第二个背包，整体复杂度是 。

难度：Mid

题目四：小基 的 City Walk 环线

这题要从“图长什么样”往状态转。每次只关心当前两条连接边之间能留下多长的可延续结构。

当两个连接点重合时，旧状态无法继续往右接，只能重开；其余情况在“重开”和“延续”之间取更优值。

难度：High

1. 小基 的货运巡线

问题描述

小基 负责一条固定货运线路。线路上有 个连续途径点，卡车初始载重为 initialWeight，最大安全载重为 maxWeight。

每个途径点会给当前载重带来一次变化：

• 正数表示装货，载重增加。
• 负数表示卸货，载重减少。
• 如果一次卸货量超过当前载重，则本次卸货后载重记为 。

你需要计算：最长的连续途径点区间长度，使得卡车在该区间内每一步更新后的载重都不超过 maxWeight。
如果不存在任何安全途径点，输出 -1。

输入格式

第一行输入三个整数 initialWeight、maxWeight、N。

第二行输入 个整数 weights[i]，表示第 个途径点对载重的影响。

输出格式

输出一个整数，表示满足安全要求的最长连续途径点个数。若不存在，输出 -1。

样例输入

5 9 4
3 2 -4 3

5 7 3
3 1 2

样例输出

2

-1

数据范围

样例	解释说明
样例 1	载重变化依次为 ，安全状态对应第 个途径点，最长连续安全段为后两个点，长度是 。
样例 2	载重变化为 ，每一步都超过上限 ，因此输出 。

题解

这题可以直接按行驶顺序做一次线性模拟。

设当前载重为 cur。遍历每个途径点的变化量 x：

1. 若 x >= 0，执行 cur += x。
2. 若 x < 0，执行 cur = max(0, cur + x)，对应“卸货超过当前载重则清空”。

每一步更新后只需要判断一次 cur <= maxWeight：

• 若成立，当前安全连续段长度 run 加一，并更新答案 best。
• 若不成立，安全连续段被打断，run 置零。

遍历结束后：

• 如果 best > 0，输出 best。
• 否则说明没有任何安全途径点，输出 -1。

正确性说明

载重变化是按顺序逐点发生的，且每个点只依赖“前一时刻载重 + 当前变化量”，不存在回溯或分支选择。
因此线性扫描得到的 cur 序列就是题目定义下的真实载重序列。

安全条件同样是逐点判定。run 恰好维护“以当前位置结尾的最长安全连续后缀长度”，best 维护历史最大值。
当遇到不安全点时把 run 归零，正好对应连续段被打断。
所以最终 best 就是最长安全连续途径点个数。

复杂度分析

• 时间复杂度：。
• 空间复杂度：（不计输入数组时）。

参考代码

• Python

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


def solve():
    ini, lim, n = map(int, input().split())
    arr = list(map(int, input().split()))

    cur = ini
    run = 0
    bst = 0

    for x in arr:
        # 先按题意更新当前载重。
        if x >= 0:
            cur += x
        else:
            cur += x
            if cur < 0:
                cur = 0

        # 再判断当前位置是否安全，维护最长连续安全段。
        if cur <= lim:
            run += 1
            if run > bst:
                bst = run
        else:
            run = 0

    print(bst if bst > 0 else -1)


if __name__ == "__main__":
    solve()

• Cpp

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

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

    long long ini, lim;
    int n;
    cin >> ini >> lim >> n;

    long long cur = ini;
    int run = 0, bst = 0;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;

        // 按题意更新载重，负载重会被截断为 0。
        if (x >= 0) {
            cur += x;
        } else {
            cur += x;
            if (cur < 0) cur = 0;
        }

        // 维护“以当前点结尾”的连续安全长度。
        if (cur <= lim) {
            ++run;
            if (run > bst) bst = run;
        } else {
            run = 0;
        }
    }

    cout << (bst > 0 ? bst : -1) << '\n';
    return 0;
}

• Java

import java.io.IOException;
import java.io.InputStream;

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

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

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int v = 0;
            while (c > ' ') {
                v = v * 10 + (c - '0');
                c = read();
            }
            return v * sgn;
        }
    }

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

        long ini = fs.nextInt();
        long lim = fs.nextInt();
        int n = fs.nextInt();

        long cur = ini;
        int run = 0, bst = 0;

        for (int i = 0; i < n; i++) {
            long x = fs.nextInt();

            // 更新载重，若小于 0 则清空。
            cur += x;
            if (cur < 0) cur = 0;

            // 维护连续安全段长度与全局最大值。
            if (cur <= lim) {
                run++;
                if (run > bst) bst = run;
            } else {
                run = 0;
            }
        }

        System.out.println(bst > 0 ? bst : -1);
    }
}

2. 小基 的排课计划

问题描述

学校共有 门课程，编号为 到 。
对每门课程 ，给出一个直接先修课 p_i：

• p_i = -1 表示课程 没有直接先修课。
• 否则 p_i 表示课程 的直接先修课编号。

先修关系按传递闭包定义：如果 是 的直接先修课，或 是 的某个直接先修课的先修课，那么 都是 的先修课。

现在需要把全部课程分配到若干学期。
同一学期中，任意两门课都不能存在先修关系。
请计算最少需要多少个学期。

已保证不存在环依赖，且 p_i != i。

输入格式

第一行输入一个整数 。

接下来 行，第 行输入一个整数 p_i。

输出格式

输出一个整数，表示最少学期数。

样例输入

5
-1
1
2
1
-1

样例输出

3

数据范围

• 
• 或
• p_i != i
• 输入保证无环

样例	解释说明
样例 1	课程链 的长度为 ，因此至少要 个学期。一个可行安排是第 学期上 ，第 学期上 ，第 学期上 。

题解

每门课只有至多一个直接先修课，因此整张图是若干棵有向树（森林），边方向是“先修课指向后继课”。

同一学期不能放一对存在先修关系的课程。
这意味着：沿着任意一条先修链，链上课程必须分到不同学期。
所以最少学期数至少是“最长先修链长度”。

另一方面，如果把每门课分配到“它在先修树中的深度层”：

• 根节点（没有先修课）在第 学期。
• 子节点在父节点学期加一。

就能保证一门课总在其所有先修课之后，且同一深度的两门课互不为祖先后代，可以同学期上。
所以这个分配是可行的，学期数恰好等于最大深度。

因此答案就是：所有课程中最大深度。

状态定义

设 dep[i] 为课程 的深度：

• 若 p_i = -1，则 dep[i] = 1。
• 否则 dep[i] = dep[p_i] + 1。

对每个课程求一次 dep[i]，取最大值即答案。

复杂度分析

• 时间复杂度：。
• 空间复杂度：。

参考代码

• Python

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


def solve():
    n = int(input())
    par = [0] * (n + 1)
    for i in range(1, n + 1):
        x = int(input())
        par[i] = 0 if x == -1 else x

    dep = [0] * (n + 1)

    def get(u):
        # 用迭代方式求深度，避免重复递归。
        if dep[u] != 0:
            return dep[u]

        st = []
        v = u
        while v != 0 and dep[v] == 0:
            st.append(v)
            v = par[v]

        # v==0 表示走到根之前；否则 dep[v] 已知。
        cur = 0 if v == 0 else dep[v]
        while st:
            x = st.pop()
            cur += 1
            dep[x] = cur
        return dep[u]

    ans = 0
    for i in range(1, n + 1):
        d = get(i)
        if d > ans:
            ans = d

    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int n;
    cin >> n;

    vector<int> par(n + 1), dep(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        par[i] = (x == -1 ? 0 : x);
    }

    function<int(int)> dfs = [&](int u) -> int {
        // dep[u] 记忆化后不再重复计算。
        if (dep[u] != 0) return dep[u];
        if (par[u] == 0) return dep[u] = 1;
        return dep[u] = dfs(par[u]) + 1;
    };

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dfs(i));
    }

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

• Java

import java.io.IOException;
import java.io.InputStream;

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

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

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int v = 0;
            while (c > ' ') {
                v = v * 10 + (c - '0');
                c = read();
            }
            return v * sgn;
        }
    }

    static int[] par;
    static int[