2023 携程春招笔试

昨天笔试录屏，做完后破防了。。。

今天上午回顾一下题目：

1. 简单 dp

A 了，就不写代码了

录屏截屏

2. 字符串拼接

简单模拟题，直接字符串拼接搞定

3. 高数求导求极值。。。

想复杂了。。。耗费了不少时间。。。

‍

‍

解方程

‍

import java.util.Scanner;

/**
 * Description:
 * date: 2023/03/08 上午 9:25
 *
 * @author Quan
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int v0 = in.nextInt(), x = in.nextInt(), y = in.nextInt();

        double ans =  2 * Math.sqrt(y / x) - (v0 / x * 1.0);
        System.out.println(ans);
    }
}

// 0 1 2
// 2.8284271247461903
​

‍

‍

4. 状态 dp + 01 背包

‍

耗费了 1 小时，早知道不去做这道题，专心攻克第三道算了。。。

‍

import java.util.Scanner;

/**
 * Description:
 * date: 2023/03/07 下午 10:09
 *
 * @author Quan
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt(), x = in.nextInt();
        int[] A = new int[n + 1];
        int[] B = new int[n + 1];
        for (int i = 1; i <= n; i++) A[i] = in.nextInt();
        for (int i = 1; i <= n; i++) B[i] = in.nextInt();

        long[][][] dp = new long[n + 1][x + 1][3];
        // dp[i][j][0] - 不买
        // dp[i][j][1] - 原价买
        // dp[i][j][2] - 半价买

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= x; j++) {
                // 当前半价买，前一个必须原价买
                if (i > 1 && j - A[i] / 2 >= A[i - 1]) {
                    // j - A[i] / 2 >= A[i - 1]：剩下的钱要能够买前一个
                    dp[i][j][2] = dp[i - 1][j - A[i] / 2][1] + B[i];
                }

                // 原价买
                if (j >= A[i]) {
                    // 要么不买，要么在原价和半价中选择最大的
                    dp[i][j][1] = Math.max(dp[i - 1][j - A[i]][0],
                            Math.max(dp[i - 1][j - A[i]][1], dp[i - 1][j - A[i]][2]) + B[i]
                    );
                }

                // 上面的是01背包逻辑，下面则是状态转移，记录最大的数值
                dp[i][j][0] = Math.max(dp[i - 1][j][0], Math.max(dp[i - 1][j][1], dp[i - 1][j][2]));
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i][j][1]);
                dp[i][j][2] = Math.max(dp[i - 1][j][2], dp[i][j][2]);
            }
        }

        System.out.println(max(dp[n][x][0], dp[n][x][1], dp[n][x][2]));
    }

    private static long max(long a, long b, long c) {
        return Math.max(a, Math.max(b, c));
    }
}

// 输入
4 7
2 2 6 2
3 4 5 1

// 输出
12
​