笔试时间: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 
点赞 16
评论 9
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务