模拟笔试 - 卡码网周赛第三十一期（23年百度笔试真题）

本文主要是介绍模拟笔试 - 卡码网周赛第三十一期（23年百度笔试真题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

难度适中，动态规划出现的比例还是比较高的，要好好掌握，二分查找的点也是比较灵活的。（A卷和B卷第一道题是一样的）

题目一：讨厌鬼的组合帖子

思路：这个题算是一个还不错的题；

本质就是：一个数组元素选或不选，可以达到的最大绝对值，经典动态规划入门题了，重要的就是能不能看到这个本质。

import java.util.Scanner;public class taoTanGui {public static void main(String[] args) {// 创建 Scanner 对象用于读取输入Scanner sc = new Scanner(System.in);// 读取整数 nint n = sc.nextInt();// 创建长度为 n 的数组 a, b, clong[] a = new long[n];long[] b = new long[n];long[] c = new long[n];// 读取数组 a 的值for (int i = 0; i < n; i++) {a[i] = sc.nextLong();}// 读取数组 b 的值并计算 c[i] = a[i] - b[i]for (int i = 0; i < n; i++) {b[i] = sc.nextLong();c[i] = a[i] - b[i];}// 创建二维 dp 数组，dp[i][0] 和 dp[i][1] 分别表示状态 i 的最小值和最大值// i 表示 选1个，选2个，选3 个，选 4个long[][] dp = new long[n + 1][2];// 初始化 dp 数组中的所有元素为 0// dp[0][0] = 0;// dp[0][1] = 0;// 计算 dp 数组for (int i = 0; i < n; i++) {// 选中当前元素的情况dp[i + 1][0] = Math.min(dp[i][0], dp[i][1]) + c[i];dp[i + 1][1] = Math.max(dp[i][0], dp[i][1]) + c[i];// 不选当前元素的情况dp[i + 1][0] = Math.min(dp[i][0], dp[i + 1][0]);dp[i + 1][1] = Math.max(dp[i][1], dp[i + 1][1]);}// 计算最终结果（Math.abs()是取绝对值的api）long ans = Math.max(Math.abs(dp[n][0]), Math.abs(dp[n][1]));// 输出结果System.out.println(ans);// 关闭 Scanner 对象sc.close();}
}

题目二：小红的16版方案

思路和代码

看到这种题，要有一个思想：二分查找，折半搜索最大的符合条件的版本号；

如何判断当前版本是否符合条件，可以使用 差分数组，其可以看错前缀和的逆过程，一定要掌握！

这段代码使用二分查找的思想，结合差分数组和前缀和的技巧来解决一个区间操作的最大化问题。通过逐步尝试更多的查询，找出能够满足条件的最大查询数量。

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取 n 和 m，n 表示数组 a 的长度，m 表示查询的数量int n = sc.nextInt();int m = sc.nextInt();// 初始化数组 a，用于存储 n 个元素long[] a = new long[n + 1];for (int i = 1; i <= n; i++) {a[i] = sc.nextLong(); // 读取数组 a 的值}// 创建二维数组 arr，用于存储 m 个查询，每个查询包含左右边界 l 和 rList<int[]> arr = new ArrayList<>();for (int i = 0; i < m; i++) {int l = sc.nextInt();int r = sc.nextInt();arr.add(new int[] { l, r }); // 将每个查询的 [l, r] 存入列表}// 初始化左右边界 l 和 r，用于二分查找的范围int l = 1;int r = m;// 二分查找，寻找最大的满足条件的 midwhile (l <= r) {int mid = (l + r) / 2; // 计算中间值// 创建数组 A，长度为 n + 2 用于差分数组的计算int[] A = new int[n + 2];// 根据当前 mid 值，应用前 mid 个查询，计算差分数组 Afor (int i = 0; i < mid; i++) {int[] query = arr.get(i);int aStart = query[0];int aEnd = query[1];A[aStart] += 1;A[aEnd + 1] -= 1;}// 使用标志位 ok 来判断当前差分结果是否满足条件boolean ok = true;// 计算实际数组 A 中的每个值，判断是否超过数组 a 中对应位置的值for (int i = 1; i <= n && ok; i++) {A[i] += A[i - 1]; // 计算前缀和if (A[i] > a[i]) {ok = false; // 如果差分数组的值大于原数组 a 的值，则不满足条件}}// 根据 ok 的结果调整二分查找的上下界if (ok) {l = mid + 1; // 如果条件满足，增加下界 l} else {r = mid - 1; // 如果不满足条件，减小上界 r}}// 输出结果，l - 1 是最大的满足条件的 midSystem.out.println(l - 1);sc.close(); // 关闭 Scanner}
}

读取输入:
- int n = sc.nextInt(); 和 int m = sc.nextInt();：分别读取整数 n 和 m，表示数组的大小和查询的数量。
- long[] a = new long[n + 1];：创建一个大小为 n+1 的数组 a，索引从 1 开始存储。
- for (int i = 1; i <= n; i++) a[i] = sc.nextLong();：从控制台读取数组 a 的值。
读取查询区间:
- List<int[]> arr = new ArrayList<>();：创建一个列表 arr 用于存储查询的左右区间 [l, r]。
- for (int i = 0; i < m; i++) { ... }：循环读取 m 个查询的左右边界 l 和 r，并将它们以数组的形式存入 arr 列表。
初始化二分查找的上下界:
- int l = 1; int r = m;：初始化左右边界 l 和 r 用于二分查找。
二分查找:
- while (l <= r) { ... }：进入二分查找循环，循环条件是 l <= r。
- int mid = (l + r) / 2;：计算当前二分查找的中间值 mid。
- int[] A = new int[n + 2];：创建一个差分数组 A，用于计算前缀和。
差分数组的应用:
- for (int i = 0; i < mid; i++) { ... }：遍历前 mid 个查询，使用差分方法对数组 A 进行标记。
- A[aStart] += 1; A[aEnd + 1] -= 1;：标记差分数组的起始和结束位置。
前缀和计算与条件检查:
- for (int i = 1; i <= n && ok; i++) { ... }：遍历数组 A，计算前缀和并检查是否超过数组 a 中的值。
- if (A[i] > a[i]) ok = false;：如果差分数组的值大于原数组 a 中对应位置的值，则不满足条件。
更新二分查找的上下界:
- if (ok) l = mid + 1;：如果当前中间值 mid 对应的查询符合条件，则增加下界。
- else r = mid - 1;：否则减小上界。
输出结果: