拼多多笔试 拼多多笔试题 0309
笔试时间：2025年03月09 春招实习
历史笔试传送门：
第一题
题目：传送门1
多多在玩一个传送门游戏。游戏开始时少少在一维数轴的x=0处。他有n个传送门，每个传送门都有一个传送值ai，他能使用该传送门从x=t位置传送到x=t+ai，传送门是消耗品，只能使用一次。同时他还有一个"反转"技能，使用该技能可以立即从位置 x=t"反转"到x=-t。少少可以以任意顺序使用这些传送门，可以在任何时候使用"反转"技能(最多用一次，也可以不用)，问用完所有传送门后，少少到初始位置x=0最远的距离为多少?
输入描述
第一行为一个正整数 n(1 ≤ n ≤ 10^5)
第二行为n个整数a1,a2,...,an(-10^4 < ai ≤ 10^4)
输出描述
输出用完所有传送门后，少少到初始位置距离的最大值。
说明：对于 60% 的数据，1 <= n <= 10对于 100%的数据，1 <= n <= 10^5,-10^4 <= ai <= 10^4
样例输入
4
1 -2 3 -4
样例输出
10
说明：最初少少在位置x=0处;他先选择使用第 2,4个传送门，到达位置x=0+a2+a4=0-2-4=-6，然后他使用技能“反转”，到达位置x=6，最后选择第 1,3 个传送门，到达位置,x=6+a1+a3=6+1+3=10，与初始位置距离最大为10。
参考题解
由于可以任意顺序使用传送门，最优的做法可以是先把所有到传送值为负的传送门用了，之后使用一次反转再用所有传送值为正的门。那么对所有元素求他们绝对值的和就是最终答。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
long long res = 0;
for (int x : a) {
res += abs(x);
}
cout << res << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long res = 0; // 用 long 来存储结果，避免大数溢出
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
res += Math.abs(x);
}
System.out.println(res);
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def main():
n = int(input().strip())
arr = list(map(int, input().strip().split()))
res = sum(abs(x) for x in arr)
print(res)
if __name__ == "__main__":
main()
第二题
题目：传送门2
多多在玩一个传送门游戏。游戏开始时多多在一维数轴的x=0处。他有n个传送门，每个传送门都有一个传送值ai，他能使用该传送门从x=t位置传送到x=t+ai，传送门是消耗品，只能使用一次。同时他还有一个"反转"技能，使用该技能可以立即从位置 x=t"反转"到x=-t。多多必须从1-n依次使用这些传送门，可以在任何时候使用"反转"技能(最多用一次，也可以不用)，问在传送过程中，多多到初始位置x=0最远的距离为多少?
输入描述
第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行为n个整数a1,a2,...,an(-10^9 < ai ≤ 10^9)
输出描述
输出在传送过程中，少少到初始位置距离的最大值。
补充说明：对于 60% 的数据，1 <= n <= 10:对于 100%的数据，1 <= n <= 10^5, -10^9 <= ai <= 10^9
样例输入一
4
1 1 -1 1
样例输出一
3
最初少少在位置x=0处;他先依次使用前2个传送门，到达位置x=0+a1+a2=0+1+1=2，与初始位置距离为2。然后他使用技能“反转”，到达位置=-2与初始位置距离为2，再使用第3个传送门，到达位置x=-2+a3=-2-1=-3，与初始距离为3。最后使用第4个传送门，到达位x=-3+a4=-3+1=-2与初始位置距离为2，在传送的过程中，与初始位置距离最大为 3
样例输入二
5
1 -4 10 -30 2
样例输出二
37
说明少少在使用过前3个传送门后到达x=7;此时使用一次“反转”，到达 x=-7;再使用第 4 个传送门到达x=-37，此时与初始位置距离最远为37
参考题解
动态规划。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(2, vector<long long>(2)));
dp[0][0][0] = dp[0][0][1] = dp[0][1][0] = dp[0][1][1] = 0;
for (int i = 1; i <= n; i++) {
int v = a[i - 1];
dp[i][0][0] = dp[i - 1][0][0] + v;
dp[i][0][1] = dp[i - 1][0][1] + v;
dp[i][1][0] = min({-dp[i - 1][0][0] + v, -dp[i - 1][0][1] + v, dp[i - 1][1][0] + v, dp[i - 1][1][1] + v});
dp[i][1][1] = max({-dp[i - 1][0][0] + v, -dp[i - 1][0][1] + v, dp[i - 1][1][0] + v, dp[i - 1][1][1] + v});
}
long long res = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
res = max(res, abs(dp[i][j][k]));
}
}
}
cout << res << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// dp[i][j][k] 与 C++ 中的三维 dp 对应
long[][][] dp = new long[n + 1][2][2];
// Java 数组元素默认初始化为 0，因此以下初始化可省略：
// dp[0][0][0] = dp[0][0][1] = dp[0][1][0] = dp[0][1][1] = 0;
for (int i = 1; i <= n; i++) {
int v = a[i - 1];
dp[i][0][0] = dp[i - 1][0][0] + v;
dp[i][0][1] = dp[i - 1][0][1] + v;
dp[i][1][0] = Math.min(
Math.min(-dp[i - 1][0][0] + v, -dp[i - 1][0][1] + v),
Math.min(dp[i - 1][1][0] + v, dp[i - 1][1][1] + v)
);
dp[i][1][1] = Math.max(
Math.max(-dp[i - 1][0][0] + v, -dp[i - 1][0][1] + v),
Math.max(dp[i - 1][1][0] + v, dp[i - 1][1][1] + v)
);
}
long res = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
res = Math.max(res, Math.abs(dp[i][j][k]));
}
}
}
System.out.println(res);
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def main():
import sys
data = sys.stdin.read().strip().split()
n = int(data[0])
a = list(map(int, data[1:]))
# 建立与 C++ 相同结构的三维列表 dp
dp = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(n + 1)]
for i in range(1, n + 1):
v = a[i - 1]
dp[i][0][0] = dp[i - 1][0][0] + v
dp[i][0][1] = dp[i - 1][0][1] + v
dp[i][1][0] = min(
-dp[i - 1][0][0] + v,
-dp[i - 1][0][1] + v,
dp[i - 1][1][0] + v,
dp[i - 1][1][1] + v
)
dp[i][1][1] = max(
-dp[i - 1][0][0] + v,
-dp[i - 1][0][1] + v,
dp[i - 1][1][0] + v,
dp[i - 1][1][1] + v
)
res = 0
for i in range(n + 1):
for j in range(2):
for k in range(2):
res = max(res, abs(dp[i][j][k]))
print(res)
if __name__ == "__main__":
main()
第三题
题目：爱读书
多多很喜欢读书，现在多多有一本书，书有n页，每读完一页，多多都可以获得ai的知识量。正常情况下，多多每分钟可以读完一页，但是多多还有一个能力，可以在一分钟内读完连续两页的内容，只不过能获取的知识量只有正常读完两页知识量之和的二分之一。现在多多只有m分钟的时间用来读完这本书，请你告诉多多他最多可以获得多少的知识。
输入描述
输入两行
第一行包含两个整数n和m(1<=n,m<=1000),表示书的页数和用来读书的时间。
第二行包含n个数字，每个数字ai(0<=ai<=10000)表示第i页的知识量。
输出描述
输出一行，包含一个数字ans，表示最大可获取的知识量，输出的结果保留一位小数，如果在m分钟内不能读完一本书，输出"-1"
样例输入一
4 1
1 2 3 4
样例输出一
-1
样例输入二
5 3
1 2 3 2 1
样例输出二
6.0
使用能力读完1、2两页，获取知识量1.5
第3页正常读，获取知识量3
使用能力读完4、5两页，获取知识量1.5
花费三分钟总计获得6的知识量
参考题解
考虑动态规划，dp[i][j]：i 表示前 i 个元素，用了 j 时间，能获得的最大知识是多少
状态转移方程为：
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + A[i - 1])，花一分钟读一页
dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + (A[i - 1] + A[i - 2]) / 2)，花一分钟读两页
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin >> A[i];
}
vector<vector<double>> dp(n + 1, vector<double>(m + 1, -1));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (dp[i - 1][j - 1] != -1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + A[i - 1]);
}
if (i >= 2 && dp[i - 2][j - 1] != -1) {
double x = A[i - 1] + A[i - 2];
dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + x / 2);
}
}
}
if (dp[n][m] == -1) {
cout << -1 << endl;
} else {
cout << fixed << setprecision(1) << dp[n][m] << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] A = new int[n];
for(int i = 0; i < n; i++) {
A[i] = sc.nextInt();
}
// 构建 dp 数组，初始全部设为 -1
double[][] dp = new double[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], -1);
}
dp[0][0] = 0.0; // 初始条件
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
// 1. 若 dp[i-1][j-1] 有效，则尝试选 A[i-1]
if (dp[i - 1][j - 1] != -1) {
double candidate = dp[i - 1][j - 1] + A[i - 1];
dp[i][j] = Math.max(dp[i][j], candidate);
}
// 2. 若 dp[i-2][j-1] 有效，且 i >= 2，则尝试选 A[i-1] + A[i-2] 的平均值
if (i >= 2 && dp[i - 2][j - 1] != -1) {
double x = A[i - 1] + A[i - 2];
double candidate = dp[i - 2][j - 1] + x / 2.0;
dp[i][j] = Math.max(dp[i][j], candidate);
}
}
}
double result = dp[n][m];
if (result == -1) {
System.out.println(-1);
} else {
// 输出保留 1 位小数
System.out.printf("%.1f\n", result);
}
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def main():
import sys
data = sys.stdin.read().strip().split()
n, m = map(int, data[:2])
A = list(map(int, data[2:]))
# 建立 dp 数组，初始值设为 -1
dp = [[-1.0 for _ in range(m + 1)] for _ in range(n + 1)]
dp[0][0] = 0.0
for i in range(1, n + 1):
for j in range(1, m + 1):
# 情况1：dp[i-1][j-1] 有效，考虑仅选 A[i-1]
if dp[i - 1][j - 1] != -1:
candidate = dp[i - 1][j - 1] + A[i - 1]
dp[i][j] = max(dp[i][j], candidate)
# 情况2：dp[i-2][j-1] 有效，i >= 2 时选 (A[i-2] + A[i-1]) / 2
if i >= 2 and dp[i - 2][j - 1] != -1:
x = A[i - 1] + A[i - 2]
candidate = dp[i - 2][j - 1] + x / 2.0
dp[i][j] = max(dp[i][j], candidate)
result = dp[n][m]
if result == -1:
print(-1)
else:
# 输出保留 1 位小数
print(f"{result:.1f}")
if __name__ == "__main__":
main()
#拼多多##拼多多实习##拼多多笔试##拼多多求职进展汇总#2025打怪升级记录，大厂笔试合集
投递拼多多集团-PDD等公司10个岗位 >
查看4道真题和解析