笔试时间：2025年03月09 春招实习

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：传送门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