拼多多笔试,有难度!(0329春招实习笔试真题解析)

5 9 4
3 2 -4 3

2

5 7 3
3 1 2

-1

#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;
}

第二题

在线做题链接：https://niumacode.com/

题意

多多的学校有 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 门课程没有直接先修课。

输出描述

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

示例1：

输入：

5
-1
1
2
1
-1

输出：

3

思路与代码

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

#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;
}

第三题

在线做题链接：https://niumacode.com/

题意

辰辰参加某知名的在线答题栏目，由于他表现出色获得了比赛的冠军，并获得了节目组给予的丰富奖励；但是节目组希望在颁奖环节再考验辰辰，请同样作为选手的你帮帮辰辰。首先，节目组提供了 N 种奖品，每种奖品的价值记为 Vi；同时节目组提供给辰辰 两个背包，每种奖品最多只能放入其中的一个背包里；另外，节目组还设置了一个额外的障碍：每个背包中任意两件奖品的价值差不能超过 T。 现在的问题是：在这样的约束下，辰辰最多能带走多少件奖品？

输入描述

第一行输入两个正整数 N 和 T： N：节目组提供的奖品数量； T：约定的同一个背包里任意两件奖品价值差的阈值。 接下来输入 N 行，每行一个数 Vi，代表相应的奖品价值。 数据范围：N≤500000，T≤50000000，Vi≤50000000。

输出描述

输出一个正整数，代表辰辰最多能带走的奖品件数。

示例1：

输入：

6 3
5
4
2
1
8
10

输出：

5

说明： 奖品价值为 [5, 4, 2, 1, 8, 10]，阈值 T=3。 最优分配方式： 背包 1：{1, 2, 4}（价值差最大为 4−1=3，满足 T=3）； 背包 2：{8, 10}（价值差为 10−8=2≤3，满足条件）； 共带走 3+2=5 件奖品，这是能取到的最大值。

思路与代码

核心思路：两个背包的奖品（排序 + 双指针 + 前后缀分解） 求两个不相交且内部极差不超过 maxDiff 的子数组的最大长度和。 首先对价值数组升序排序，使问题转化为在序列上找两个互不重叠的合法区间。 使用双指针（滑动窗口）分别从左向右预处理出以 i 结尾的最长合法区间长度 prefixMax[i]，并维护其前缀最大值； 再从右向左预处理出以 i 开头的最长合法区间长度 suffixMax[i]，并维护其后缀最大值。 最后枚举分割点 i，答案即为 max(prefixMax[i] + suffixMax[i+1])。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numPrizes, maxDiff;
if (!(cin >> numPrizes >> maxDiff)) return 0;

    vector<int> prizes(numPrizes);
for (int i = 0; i < numPrizes; ++i) {
        cin >> prizes[i];
    }

    sort(prizes.begin(), prizes.end());

    vector<int> prefixMax(numPrizes, 0);
    vector<int> suffixMax(numPrizes, 0);

    int leftPtr = 0;
for (int i = 0; i < numPrizes; ++i) {
while (prizes[i] - prizes[leftPtr] > maxDiff) {
            leftPtr++;
        }
        int currentLen = i - leftPtr + 1;
if (i > 0) {
            prefixMax[i] = max(prefixMax[i - 1], currentLen);
        } else {
            prefixMax[i] = currentLen;
        }
    }

    int rightPtr = numPrizes - 1;
for (int i = numPrizes - 1; i >= 0; --i) {
while (prizes[rightPtr] - prizes[i] > maxDiff) {
            rightPtr--;
        }
        int currentLen = rightPtr - i + 1;
if (i < numPrizes - 1) {
            suffixMax[i] = max(suffixMax[i + 1], currentLen);
        } else {
            suffixMax[i] = currentLen;
        }
    }

    int maxTotalPrizes = prefixMax[numPrizes - 1];
for (int i = 0; i < numPrizes - 1; ++i) {
if (prefixMax[i] + suffixMax[i + 1] > maxTotalPrizes) {
            maxTotalPrizes = prefixMax[i] + suffixMax[i + 1];
        }
    }

    cout << maxTotalPrizes << "\n";

return 0;
}

第四题

在线做题链接：https://niumacode.com/

题意

背景：多多规划 city walk 路径，城市由多条平行主干道组成，每条主干道包含若干景点，主干道之间通过小路连接。路径约束（必须严格遵守）： 起点与终点：可以从任意主干道的任意景点出发，最终必须回到出发点（形成一个闭合回路）。 节点访问：每个景点只能走一次，不能重复。 行走范围：可以走主干道，也可以走连接主干道的小路。 路径选择：无需覆盖主干道上所有景点，可选择性经过。 问题目标：已知主干道或小路上连接两个景点的长度为 1，求多多能规划出的 经过景点数量最多 的 city walk 路径的长度（即经过的景点总数）。

输入描述

第一行：一个整数 t (1≤t≤103)，表示测试用例数量。 每个测试用例： 第一行：一个整数 n (2≤n≤104)，表示主干道数量。 第二行：n 个整数 c1,c2,...,cn (2≤ci≤10^5)，其中 ci 表示第 i 条主干道上的景点数量。 第三行：n−1 个整数 a1,a2,...,an−1 (1≤ai≤ci)，表示第 i 条主干道与第 i+1 条主干道连接点：ai 是第 i 条主干道的第一个景点编号。 第四行：n−1 个整数 b1,b2,...,bn−1 (1≤bi≤ci+1)，表示第 i 条主干道与第 i+1 条主干道连接点：bi 是第 i+1 条主干道的最后一个景点编号。 关键连接规则： 第 i 条主干道的第一个景点（编号 ai）与第 i+1 条主干道的最后一个景点（编号 bi）之间有小路连接，长度为 1。 主干道内部景点是顺序连接的（例如第 i 条主干道的景点编号 1,2,...,ci 依次线性相连，长度均为 1）。

输出描述

对于每个测试用例，输出一个整数，代表最长 city walk 路径的长度

补充说明

1≤T≤3 1≤n≤10^6 0≤m≤10^6 1≤w≤n 0≤ai,bi≤10^9 单个测试用例中所有测试数据的 n 之和不超过 10^6

示例1：

输入：

3
4
3 4 3 3
1 2 2
2 2 3
2
5 6
5
1
3
3 5 2
1 1
3 5

输出：

7
11
8

说明： 第一个测试用例的最长路径如下，我们无法把路径拓展到主干道1，否则主书道2上的节点2会被访问2次

思路与代码

特定图结构上的最长路 DP。观察路径特征，每个主干道上的点只能走一次。 采用从右向左逆序 DP。定义 dp[i] 为从第 i 条主干道的入口走到最后的最大节点数。 状态转移：对于第 i 条主干道： 若首尾连接点不同（inPoint[i] != outPoint[i]）：可以选择绕行干道其余部分再从 outPoint[i] 出去， 转移方程为 pointsOnRoad[i] - abs(inPoint[i] - outPoint[i]) + 1 + dp[i+1]；也可以止步于此（取 pointsOnRoad[i]）。两者取最大值。 若相同（inPoint[i] == outPoint[i]）：为了不走回头路，无法继续向右拓展，只能止步，取 pointsOnRoad[i]。 最终答案：枚举所有的横向小路入口作为起点，结合 dp[i+1] 更新全局最大值。

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

void solve() {
    int numRoads;
    cin >> numRoads;

    vector<int> pointsOnRoad(numRoads + 1);
for (int i = 1; i <= numRoads; ++i) {
        cin >> pointsOnRoad[i];
    }

    vector<int> inPoint(numRoads + 1);
for (int i = 1; i < numRoads; ++i) {
        cin >> inPoint[i];
    }

    vector<int> outPoint(numRoads + 1);
for (int i = 1; i < numRoads; ++i) {
        cin >> outPoint[i];
    }

    vector<int> dp(numRoads + 1, 0);
    dp[numRoads] = pointsOnRoad[numRoads];

for (int i = numRoads - 1; i > 1; --i) {
if (inPoint[i] != outPoint[i]) {
            int walkThrough = pointsOnRoad[i] - abs(inPoint[i] - outPoint[i]) + 1 + dp[i + 1];
            dp[i] = max(pointsOnRoad[i], walkThrough);
        } else {
            dp[i] = pointsOnRoad[i];
        }
    }

    int maxPathLength = 0;
for (int i = 1; i < numRoads; ++i) {
        int currentPath = abs(inPoint[i] - outPoint[i]) + 1 + dp[i + 1];
if (currentPath > maxPathLength) {
            maxPathLength = currentPath;
        }
    }

    cout << maxPathLength << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numTestCases;
if (cin >> numTestCases) {
while (numTestCases--) {
            solve();
        }
    }
return 0;
}

我们是一个针对技术岗（前后端开发、测试、测开、大数据开发、大模型、ai等相关岗位）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整六年的时间，带领900+学员斩获4000+中大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！

万诺coding

我们主要是针对有一定基础的同学提供全程一对一笔试、面试辅导，针对每个同学不同的情况定制内容，包括但不限于“笔试及面试算法”/“基础八股/“项目及实习梳理”/“面试技巧”/“面试复盘”等内容。

摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。摸底测试后，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。 

承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。

有兴趣的同学可以扫码添加我们的微信（whynotlab）