蓝桥杯之阶段考核

📖 Day 7：阶段考核 - 蓝桥杯官方模拟赛（限时 4 小时）

📖 一、如何高效完成模拟赛？

模拟赛是一种接近真实竞赛的训练方式。要高效完成模拟赛，需要掌握以下策略：

1. 赛前准备

✅ 环境搭建：确保 Java 开发环境、IDE（如 IntelliJ IDEA、Eclipse、VS Code）正常运行，输入输出调试正常。
✅ 熟悉常见模板：准备好 DFS、回溯、动态规划、位运算等常用算法模板，避免比赛时临时推导。
✅ 阅读题目速度：比赛时，快速理解题意，确定题目涉及的算法类型。

2. 赛时策略

📌 ① 先做简单题：先做 确定思路的题，比如基础遍历、贪心算法、双指针等题目。
📌 ② 观察数据规模：如果数据规模 ≤10^6，考虑 O(n) 或 O(n log n) 解法；如果 ≤100，考虑 O(n²) 解法；如果 ≤20，考虑回溯 + 剪枝。
📌 ③ 分析边界情况：比如 n=1、n=0、极端输入情况，防止 ArrayIndexOutOfBoundsException。
📌 ④ 超时优化：如果代码超时，优化时间复杂度（如 O(n²) → O(n log n)），或改用位运算、哈希表、前缀和等加速。

3. 赛后复盘

🔍 ① 查看错误代码：分析错误原因，如 索引越界、浮点精度、整数溢出、边界处理错误。
🔍 ② 记录思路：如果某题没做出来，找出 最优解法 并理解其时间复杂度。
🔍 ③ 归纳高频考点：整理本场比赛涉及的算法，找出自己薄弱的地方，强化训练。

📖 二、常见题型及解法

模拟赛一般包含以下几种类型的题目，我们来看几道典型题目的解法：

📌 1. 经典贪心题目：区间覆盖

题目描述

给定 n 个区间 [li, ri]，选择最少数量的区间，使得区间 start 到 end 都被覆盖。

解题思路

先按 左端点排序，然后贪心地选择能覆盖更多区域的区间。
如果当前区间无法覆盖 start，返回 -1，否则更新当前 end。

代码实现

import java.util.*;public class IntervalCover {public static int minIntervals(int[][] intervals, int start, int end) {Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); // 按左端点排序int count = 0, curEnd = start, i = 0;while (curEnd < end) {int maxEnd = curEnd;while (i < intervals.length && intervals[i][0] <= curEnd) {maxEnd = Math.max(maxEnd, intervals[i][1]);i++;}if (maxEnd == curEnd) return -1; // 无法覆盖curEnd = maxEnd;count++;}return count;}public static void main(String[] args) {int[][] intervals = {{1, 3}, {2, 5}, {3, 6}, {5, 8}};System.out.println(minIntervals(intervals, 1, 8)); // 输出 2}
}

时间复杂度：O(n log n)（排序） + O(n)（遍历） = O(n log n)。

📌 2. 经典回溯题目：全排列

题目描述

给定一个不含重复数字的数组 nums，返回所有可能的全排列。

解题思路

使用 回溯 + 递归，每次选择一个数字加入排列，回溯时撤销选择。

代码实现

import java.util.*;public class Permutations {public static List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);return result;}private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, boolean[] used) {if (tempList.size() == nums.length) {result.add(new ArrayList<>(tempList));return;}for (int i = 0; i < nums.length; i++) {if (!used[i]) {used[i] = true;tempList.add(nums[i]);backtrack(result, tempList, nums, used);tempList.remove(tempList.size() - 1);used[i] = false;}}}public static void main(String[] args) {int[] nums = {1, 2, 3};System.out.println(permute(nums));}
}

时间复杂度：O(n!)，因为每个元素都会被排列。

📌 3. 经典动态规划题目：最长递增子序列（LIS）

题目描述

给定一个整数数组 nums，找到其中最长递增子序列的长度。

解题思路

dp[i] 代表以 nums[i] 结尾的最长递增子序列长度。
对于每个 nums[i]，遍历 nums[j] (j < i)，如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)。

代码实现

import java.util.*;public class LongestIncreasingSubsequence {public int lengthOfLIS(int[] nums) {int n = nums.length, maxLen = 0;int[] dp = new int[n];Arrays.fill(dp, 1);for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLen = Math.max(maxLen, dp[i]);}return maxLen;}public static void main(String[] args) {LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};System.out.println("最长递增子序列长度: " + lis.lengthOfLIS(nums)); // 输出 4}
}

时间复杂度：O(n²)，优化可用 O(n log n)（二分查找 + 贪心）。