拼多多笔试 拼多多笔试真题解析 0329春招实习笔试

笔试时间：2026年3月29日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：货车运输

题目

多多需要驾驶卡车按照指定的路线运输货物，路线沿途设有多个途径点。每个途径点会对卡车的载重产生影响：部分途径点需要装载货物（增加载重），部分途径点需要卸载货物（减少载重）。若卡车的货物载重小于途径点需卸载的货物重量，则车辆需全部卸载后再前往下一个途径点。

卡车有初始载重 initialWeight，为了确保行车安全，卡车的载重必须始终小于等于最大载重 maxSafeWeight。

你的任务是：高效计算出最大的连续途径点个数，使得多多在这些连续途径点行驶时，始终保持载重不超过安全限制。如果所有途径点都无法满足安全运输的条件，则输出 -1。

输入描述

输入共两行：

• 第一行包含 3 个整数：initialWeight、maxWeight、N，分别表示卡车初始载重、卡车最大安全载重、途径点数量。
• 约束条件：1 ≤ maxWeight ≤ 10000，1 ≤ n ≤ 100000，0 ≤ initialWeight ≤ maxWeight。
• 第二行包含 N 个整数 weights[n]，表示途径点对卡车实际载重的影响：正数为装载（增加载重），负数为卸载（减少载重）。
• 约束条件：对任意一个途径点 i，均有 -100 ≤ weights[i] ≤ 100。

输出描述

输出一行，为满足条件的最大连续途径点个数；如果所有途径点都无法满足安全运输条件，则输出 -1。

样例输入1

5 9 4
3 2 -4 3

样例输出1

2

样例说明： 初始载重为 5，最大安全载重为 9，途径点有 4 个（记为 A、B、C、D）。

• 抵达 A：载重 = 5 + 3 = 8（≤ 9，安全）
• 抵达 B：载重 = 8 + 2 = 10（> 9，不安全）
• 抵达 C：载重 = 10 - 4 = 6（≤ 9，安全）
• 抵达 D：载重 = 6 + 3 = 9（≤ 9，安全）

最大的连续安全途径点为 C 和 D，共 2 个，因此输出 2。

样例输入2

5 7 3
3 1 2

样例输出2

-1

样例说明： 初始载重为 5，最大安全载重为 7，途径点有 3 个。所有途径点累加后均超过 7，因此输出 -1。

参考题解

解题思路： 模拟 / 贪心。扫一遍数组模拟载重变化。维护当前载重 currentWeight 和当前连续合法点数 currentContinuousPoints。遍历时 currentWeight += pointWeight，若 currentWeight < 0 则强制置零（卸载完）。随后判断：若 currentWeight <= maxSafeWeight，则连续点数加一并更新答案最大值；若超载，则断开连续段，重置连续点数为 0。

C++：

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int initialWeight, maxSafeWeight, numPoints;
    if (!(cin >> initialWeight >> maxSafeWeight >> numPoints)) return 0;

    int maxContinuousPoints = 0;
    int currentContinuousPoints = 0;
    int currentWeight = initialWeight;

    for (int i = 0; i < numPoints; ++i) {
        int pointWeight;
        cin >> pointWeight;
        currentWeight += pointWeight;
        if (currentWeight < 0) {
            currentWeight = 0;
        }
        if (currentWeight <= maxSafeWeight) {
            currentContinuousPoints++;
            if (currentContinuousPoints > maxContinuousPoints) {
                maxContinuousPoints = currentContinuousPoints;
            }
        } else {
            currentContinuousPoints = 0;
        }
    }

    if (maxContinuousPoints == 0) {
        cout << -1 << "\n";
    } else {
        cout << maxContinuousPoints << "\n";
    }
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int initialWeight = scanner.nextInt();
        int maxSafeWeight = scanner.nextInt();
        int numPoints = scanner.nextInt();

        int maxContinuousPoints = 0;
        int currentContinuousPoints = 0;
        int currentWeight = initialWeight;

        for (int i = 0; i < numPoints; i++) {
            int pointWeight = scanner.nextInt();
            currentWeight += pointWeight;
            if (currentWeight < 0) {
                currentWeight = 0;
            }
            if (currentWeight <= maxSafeWeight) {
                currentContinuousPoints++;
                if (currentContinuousPoints > maxContinuousPoints) {
                    maxContinuousPoints = currentContinuousPoints;
                }
            } else {
                currentContinuousPoints = 0;
            }
        }

        if (maxContinuousPoints == 0) {
            System.out.println(-1);
        } else {
            System.out.println(maxContinuousPoints);
        }
    }
}

Python：

import sys

def main():
    data = sys.stdin.read().split()
    idx = 0
    initial_weight = int(data[idx]); idx += 1
    max_safe_weight = int(data[idx]); idx += 1
    num_points = int(data[idx]); idx += 1

    max_continuous = 0
    current_continuous = 0
    current_weight = initial_weight

    for i in range(num_points):
        point_weight = int(data[idx]); idx += 1
        current_weight += point_weight
        if current_weight < 0:
            current_weight = 0
        if current_weight <= max_safe_weight:
            current_continuous += 1
            if current_continuous > max_continuous:
                max_continuous = current_continuous
        else:
            current_continuous = 0

    if max_continuous == 0:
        print(-1)
    else:
        print(max_continuous)

if __name__ == "__main__":
    main()

第二题：课程先修排课

题目

多多的学校有 n 门课程，编号从 1 到 n。

先修课定义： 只要满足以下任一条件，则课程 A 是课程 B 的先修课：

• 直接先修： 课程 A 是课程 B 的直接先修课程；
• 传递依赖： 课程 B 有一门直接先修课程 C，且课程 A 是课程 C 的先修课程。（即：先修关系具有传递性）

排课约束： 需要将所有 n 门课程分配到若干个学期中。每个学期内，不能存在两门课程 A 和 B，使得 A 是 B 的先修课。（简单说：同一个学期里，不能有"上下级"关系的两门课）

目标： 计算满足所有约束条件下，最少需要多少个学期。

输入描述

• 第一行：整数 n（1 ≤ n ≤ 2000），表示课程数量。
• 接下来 n 行：每行包含一个整数 pi。第 i 行的 pi 表示第 i 门课程的直接先修课程编号。
• 若 pi = -1，表示第 i 门课程没有直接先修课。

输出描述

输出一个整数，即排完所有课程所需的最少学期数。

样例输入

5
-1
1
2
1
-1

样例输出

3

参考题解

解题思路： 本质是求森林的最大深度（或有向无环图的最长链）。由于输入给出的是每个节点的直接前驱（父节点），且无环，可以直接使用记忆化 DFS。定义 depth[u] 表示以节点 u 结尾的最长链长度。转移方程为 depth[u] = depth[prerequisite[u]] + 1。遍历所有节点求出 depth[i]，全局最大值即为最少所需学期数。

C++：

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

vector<int> prerequisite;
vector<int> depth;

int getDepth(int u) {
    if (depth[u] != 0) {
        return depth[u];
    }
    if (prerequisite[u] == -1) {
        depth[u] = 1;
    } else {
        depth[u] = getDepth(prerequisite[u]) + 1;
    }
    return depth[u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int numCourses;
    if (!(cin >> numCourses)) return 0;

    prerequisite.resize(numCourses + 1);
    depth.resize(numCourses + 1, 0);

    for (int i = 1; i <= numCourses; ++i) {
        cin >> prerequisite[i];
    }

    int minSemesters = 0;
    for (int i = 1; i <= numCourses; ++i) {
        if (depth[i] == 0) {
            getDepth(i);
        }
        if (depth[i] > minSemesters) {
            minSemesters = depth[i];
        }
    }

    cout << minSemesters << "\n";
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    static int[] prerequisite;
    static int[] depth;

    static int getDepth(int u) {
        if (depth[u] != 0) {
            return depth[u];
        }
        if (prerequisite[u] == -1) {
            depth[u] = 1;
        } else {
            depth[u] = getDepth(prerequisite[u]) + 1;
        }
        return depth[u];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numCourses = scanner.nextInt();
        prerequisite = new int[numCourses + 1];
        depth = new int[numCourses + 1];

        for (int i = 1; i <= numCourses; i++) {
            prerequisite[i] = scanner.nextInt();
        }

        int minSemesters = 0;
        for (int i = 1; i <= numCourses; i++) {
            if (depth[i] == 0) {
                getDepth(i);
            }
            if (depth[i] > minSemesters) {
                minSemesters = depth[i];
            }
        }

        System.out.println(minSemesters);
    }
}

Python：

import sys
sys.setrecursionlimit(10000)

def main():
    data = sys.stdin.read().split()
    idx = 0
    num_courses = int(data[idx]); idx += 1

    prerequisite = [0] * (num_courses + 1)
    depth = [0] * (num_courses + 1)

    for i in range(1, num_courses + 1):
        prerequisite[i] = int(data[idx]); idx += 1

    def get_depth(u):
        if depth[u] != 0:
            return depth[u]
        if prerequisite[u] == -1:
            depth[u] = 1
        else:
            depth[u] = get_depth(prerequisite[u]) + 1
        return depth[u]

    min_semesters = 0
    for i in range(1, num_courses + 1):
        if depth[i] == 0:
            get_depth(i)
        if depth[i] >