1. 从两道真题看蓝桥杯的算法考察逻辑最近在带几个学生准备蓝桥杯发现他们刷题时有个通病拿到题目就埋头写代码结果要么超时要么逻辑漏洞百出。特别是像“质数拆分”和“明明的随机数”这类经典题目看似基础实则暗藏玄机非常能考察一个选手对算法和数据结构的理解深度。今天我就结合这两道题聊聊蓝桥杯Java组解题时除了“能跑通”之外更应该关注的那些东西——比如如何把一道题拆解成清晰的步骤如何选择合适的数据结构以及如何写出既高效又健壮的代码。这不仅仅是应付比赛更是锻炼工程思维的好机会。“质数拆分”本质上是一个动态规划问题但披着数论的外衣你需要先筛出质数再将其视为“物品”进行组合。而“明明的随机数”则是考察对Java集合框架的熟练运用和去重排序的基本功。两道题一难一易组合在一起恰好覆盖了从基础语法到中等难度算法的过渡。接下来我会先带大家吃透“明明的随机数”这道开胃菜建立信心和规范再深入“质数拆分”的核心拆解其动态规划的建模过程。你会发现把思路理清比盲目敲代码要重要得多。2. “明明的随机数”巩固基础与规范编码这道题可以说是蓝桥杯乃至许多OJ平台的“Hello World”级算法题。题目要求很简单输入N个随机整数去重后排序输出。很多新手觉得用Arrays.sort()和一层循环去重就完事了但这样往往只能过样例在性能或边界条件上会栽跟头。我们先从最直接的思路开始逐步优化。2.1 问题重述与输入输出分析题目描述通常为明明生成了N个1到1000之间的随机整数请你删去其中重复的数字并按从小到大的顺序输出。输入有两行第一行是随机整数的个数N第二行是N个用空格隔开的整数。这里有几个关键点需要预先明确这也是很多同学第一次提交就“Wrong Answer”的原因N的范围题目虽未明确但根据经验N可能很大比如10^5。这意味着O(N²)的暴力去重双重循环比较一定会超时。去重与排序的优先级必须先完成去重再对去重后的结果排序。如果先排序再去重在编码上会更简单但逻辑上依然是两个独立步骤。输出格式通常要求每个数字占一行或者用空格隔开在一行内输出务必看清题目要求。一个健壮的程序必须处理这些边界。例如当N0时程序不应该崩溃而应该无输出或输出空行。输入的数字可能不是严格在1-1000之间但只要在int范围内我们的算法就应该能处理。2.2 方案对比从暴力到优雅我们先看看几种常见的实现方案并分析其优劣。方案一排序后遍历去重这是最直观的方法。先使用Arrays.sort()对输入数组进行排序时间复杂度为O(N log N)。排序后相同的数字会相邻。然后遍历数组只输出与上一个输出不同的数字。import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } Arrays.sort(arr); // 处理边界如果数组为空则直接结束 if (n 0) { return; } // 输出第一个元素 System.out.println(arr[0]); for (int i 1; i n; i) { // 如果当前元素不等于前一个元素则输出 if (arr[i] ! arr[i - 1]) { System.out.println(arr[i]); } } } }优点逻辑清晰代码简短利用排序特性自然去重。缺点修改了原始输入数组排序操作如果后续还需要原数组则需拷贝。另外当数字范围已知且较小时有更优解。方案二利用布尔数组标记桶排序思想由于题目限定了数字范围1-1000我们可以利用这个信息。创建一个大小为1001的布尔数组boolean[] flag new boolean[1001]。遍历输入数字以该数字为下标将对应位置标记为true。最后遍历flag数组下标值即为排序去重后的结果。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); boolean[] exists new boolean[1001]; // 下标0-1000 for (int i 0; i n; i) { int num sc.nextInt(); exists[num] true; // 标记该数字存在 } for (int i 1; i 1000; i) { // 题目范围是1-1000 if (exists[i]) { System.out.println(i); } } } }优点时间复杂度为O(NM)其中M是数值范围1001在N很大时效率极高且天然完成了排序和去重。缺点严重依赖于数值范围已知且不大的前提。如果数字范围是整型这种方法会消耗巨大内存约2^31个布尔值不可行。方案三使用TreeSet最符合Java风格的解法TreeSet是Java集合框架中基于红黑树实现的有序集合它自动保证元素唯一且按自然顺序或指定比较器排序。import java.util.Scanner; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); TreeSetInteger set new TreeSet(); for (int i 0; i n; i) { set.add(sc.nextInt()); // 添加操作自动去重TreeSet自动排序 } for (Integer num : set) { System.out.println(num); } } }优点代码极其简洁完全将去重和排序的逻辑委托给TreeSet体现了Java高级API的便捷性。时间复杂度为O(N log N)与排序法相当。缺点对于算法竞赛需要了解其底层是红黑树每次插入是O(log N)。在极端追求性能的场景下可能不如方案二。但绝大多数情况下这是最佳选择。提示在蓝桥杯等竞赛中如果题目明确数值范围小如本题的1-1000方案二桶标记法是首选因为它最快且稳定。如果不确定范围或范围很大方案三TreeSet是最优雅和通用的选择。方案一则是理解基础算法流程的好例子。2.3 常见“坑点”与调试心得即便思路正确实现时也可能踩坑。这里分享几个我学生常犯的错误输入读取问题使用Scanner时在读取完数字后如果下一行还有输入比如字符串要注意用nextLine()吸收掉换行符。本题只有数字问题不大。输出格式问题题目要求每行一个数就不能输出成一行用空格隔开。务必仔细阅读输出描述。有时最后一个数字后面不能有多余空格或换行需要使用StringBuilder进行拼接控制。边界条件处理当N0或1时你的循环还能正常工作吗Arrays.sort()对空数组排序不会报错但后续的arr[0]就会数组越界。方案二的循环从1开始也需要注意N0的情况。性能考量虽然本题数据量可能不大但养成好习惯。避免在循环内进行字符串拼接如s num “\n”因为会创建大量临时对象。使用StringBuilder或直接System.out.println是更好的选择。在实际编码中我建议先写方案三因为它最不容易出错。如果追求极致性能再考虑根据题目条件换用方案二。理解每种方案背后的数据结构数组、红黑树比记住代码更重要。3. “质数拆分”动态规划与数论的结合如果说“明明的随机数”是热身那“质数拆分”就是正餐了。这道题完美地结合了数论质数筛法和动态规划背包问题是蓝桥杯考查综合能力的典型题目。题目通常描述为将某个正整数拆分为若干个不同的质数之和问有多少种拆分方法。例如2019可以被拆分成多少种不同的质数组合看到“拆分”、“多少种方法”有经验的选手立刻会联想到动态规划中的“组合问题”。但这里的“物品”不是题目直接给出的而是需要我们自己先求出来——所有小于目标数的质数。因此解题分为两个清晰的阶段第一阶段筛质数第二阶段动态规划计数。3.1 第一阶段高效筛选质数动态规划需要质数作为“物品”列表。如何快速得到所有小于目标数N的质数这里就需要用到高效的筛法。最著名的有两种埃拉托斯特尼筛法埃氏筛和欧拉筛线性筛。埃氏筛Eratosthenes Sieve原理很简单从2开始将每个质数的倍数标记为合数。public static ListInteger getPrimes(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; // 0和1不是质数 ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); // i是质数 // 标记i的所有倍数为合数 // 优化从i*i开始标记因为小于i*i的合数已被更小的质数标记过 if ((long) i * i limit) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } } return primes; }时间复杂度O(N log log N)对于N2019绰绰有余甚至N10^6也很快。优点实现简单易于理解和记忆。缺点一个合数会被多个质数标记有重复操作。欧拉筛线性筛欧拉筛保证了每个合数只被其最小的质因数标记一次从而达到线性时间复杂度O(N)。public static ListInteger getPrimesLinear(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); } // 用当前已得到的质数 primes.get(j) 去标记合数 for (int j 0; j primes.size() i * primes.get(j) limit; j) { isPrime[i * primes.get(j)] false; // 关键如果i能被当前质数整除则跳出循环 // 保证每个合数只被其最小质因子标记一次 if (i % primes.get(j) 0) { break; } } } return primes; }对于本题N2019两种筛法时间差异微乎其微。但在面对更大数据如N10^7时欧拉筛的优势会体现出来。在竞赛中如果对筛法不熟用埃氏筛足矣代码更不容易写错。注意在动态规划中我们需要的质数列表是primes。同时我们可能还需要快速判断一个数是否为质数这时isPrime布尔数组就派上用场了。在“质数拆分”问题中我们通常只需要列表。3.2 第二阶段动态规划建模与实现拿到质数列表后问题转化为给定一个目标总和S如2019和一系列互不相同的“物品”质数每个物品只能使用一次不同质数求恰好装满容量S的背包有多少种组合方式这是一个经典的0-1背包计数问题。定义状态dp[i][j]为考虑前i个质数组成总和为j的方案数。状态转移方程如下如果不选第i个质数p方案数等于前i-1个质数组成j的方案数即dp[i][j] dp[i-1][j]。如果选第i个质数p前提是j p方案数等于前i-1个质数组成j-p的方案数即dp[i][j] dp[i-1][j-p]。初始化dp[0][0] 1表示用0个质数组成0有1种方案什么都不选。其他dp[0][j] (j0) 0。最终答案dp[n][S]其中n是质数的个数。空间优化滚动数组由于dp[i][j]只依赖于dp[i-1][...]我们可以将二维数组压缩成一维数组dp[j]。但需要注意为了确保每个质数只使用一次内层循环j需要从大到小遍历。public static long countPrimeSplits(int target) { ListInteger primes getPrimes(target); // 获取所有小于等于target的质数 long[] dp new long[target 1]; dp[0] 1; // 初始化总和为0的方案数为1 for (int prime : primes) { // 0-1背包逆序更新 for (int j target; j prime; j--) { dp[j] dp[j - prime]; } } return dp[target]; }为什么内层要逆序这是0-1背包空间优化的关键。如果正序遍历当更新dp[j]时dp[j - prime]可能已经在同一轮考虑当前质数时被更新过了这意味着我们可能重复使用了当前质数多次变成了“完全背包”问题。逆序遍历保证了在更新dp[j]时dp[j - prime]还是基于“未考虑当前质数”的状态从而每个质数最多被使用一次。3.3 完整代码实现与测试将两部分结合起来并处理输入输出完整的解题代码如下import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int target sc.nextInt(); // 例如输入 2019 System.out.println(countPrimeSplits(target)); } // 埃氏筛获取质数列表 public static ListInteger getPrimes(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); if ((long) i * i limit) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } } return primes; } // 动态规划计算拆分方案数 public static long countPrimeSplits(int target) { ListInteger primes getPrimes(target); long[] dp new long[target 1]; dp[0] 1; for (int prime : primes) { for (int j target; j prime; j--) { dp[j] dp[j - prime]; } } return dp[target]; } }测试与验证输入7质数有[2,3,5,7]。拆分方式有7, 25, 223? (不行2重复了)。实际上77, 25。答案是2。程序输出2。输入10质数[2,3,5,7]。拆分23510, 3710, 22...不允许重复。答案是2。程序输出2。输入2019这是一个较大的数需要程序有较好的效率。运行上述代码可以很快得到结果具体数值需运行程序。3.4 深入思考不同与重复的边界这道题有一个非常关键的约束“不同的质数”。这直接决定了我们使用0-1背包模型。如果题目改为“可重复使用同一个质数”那就变成了完全背包计数问题其动态规划的内层循环就需要正序遍历了。// 假设质数可以重复使用完全背包问题 public static long countPrimeSplitsUnlimited(int target) { ListInteger primes getPrimes(target); long[] dp new long[target 1]; dp[0] 1; for (int prime : primes) { // 完全背包正序更新 for (int j prime; j target; j) { dp[j] dp[j - prime]; } } return dp[target]; }仅仅是一个遍历顺序的区别问题的本质就变了。在比赛时一定要像这样仔细审题抓住“不同”、“重复”、“顺序有关/无关”这些关键词它们直接决定了算法模型的选择。另一个容易混淆的点是“组合”与“排列”。本题是组合问题235和325被视为同一种所以我们的物品质数是放在外层循环的。如果是排列问题顺序不同视为不同方案则需要把目标总和放在外层循环物品放在内层。理解这些细微差别才能灵活应对变种题目。4. 算法竞赛中的实战技巧与心态通过这两道题我们不仅学习了具体解法更重要的是一种系统化的解题思维。在蓝桥杯或任何算法竞赛中时间有限压力大如何快速且正确地解决问题我结合自己的参赛和教学经验分享几点心得。4.1 四步解题法读、析、设、码读题与抽象5分钟这是最关键的一步。逐字逐句读题用笔划出关键约束数据范围N, M的大小、特殊条件是否重复、是否有序、输入输出格式。像“质数拆分”中的“不同质数”就是核心约束。将实际问题抽象成数学模型或已知算法问题背包、搜索、图论等。复杂度分析与算法设计5-10分钟根据数据范围反推可接受的算法复杂度。例如N≤20可能用指数级搜索N≤1000可能用O(N²)动态规划N≤10^5通常需要O(N log N)或O(N)的算法。设计算法步骤在草稿纸上画出状态转移或流程。细节设计与边界考虑5分钟设计数据结构用数组还是集合确定循环边界思考初始化状态。考虑极端情况空输入、最大/最小输入、结果为0或1的情况。为这些情况设计测试样例。编码与调试剩余时间将设计翻译成代码。优先保证代码清晰可读使用有意义的变量名。写完后用自己设计的边界样例和题目样例进行测试。如果出错使用打印语句或调试器定位问题是算法逻辑错误还是边界处理不当很多同学把大部分时间花在编码和调试上往往是因为前两步没做好。磨刀不误砍柴工清晰的思路能节省大量时间。4.2 Java选手的武器库与避坑指南作为Java选手我们有一些独特的优势和需要特别注意的“坑”。优势武器库丰富的集合框架ArrayList,LinkedList,HashSet,TreeSet,HashMap,PriorityQueue等。像“明明的随机数”用TreeSet复杂去重计数用HashMap能极大简化代码。强大的工具类Arrays.sort(),Collections.sort(),Math类下的各种函数。StringBuilder在需要频繁拼接字符串时如输出结果务必使用StringBuilder直接使用连接在循环中会带来巨大的性能开销。常见“坑点”输入输出效率当输入数据量极大10^5以上时Scanner可能会成为性能瓶颈。此时应换用BufferedReader。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String[] params br.readLine().split( ); int n Integer.parseInt(params[0]);整数溢出这是最隐蔽的Bug之一两个int相乘即使结果用long接收乘法运算本身也可能已经溢出。例如计算i * i时如果i接近10^5i*i就超过int范围了。解决办法是提前将操作数转为long(long) i * i。在“质数拆分”的dp计数中方案数也可能超过int范围所以dp数组要用long。递归深度Java默认的栈深度可能无法支持很深的递归如DFS搜索深度超过1万层。非尾递归的深搜要考虑用栈数据结构手动模拟或者尝试迭代解法。内存限制蓝桥杯通常内存限制为128MB或256MB。要估算数组大小例如一个int[100000][100000]的二维数组绝对会内存超限。在必须使用二维DP时考虑是否能滚动数组优化成一维。4.3 从刷题到精通如何有效练习最后谈谈练习方法。盲目刷几百道题不如精做几十道。一题多解就像我们对“明明的随机数”做的尝试用多种方法解决同一问题并分析时空复杂度差异。这能加深你对数据结构和算法的理解。举一反三做完“质数拆分”可以去找其他背包问题01背包、完全背包、多重背包的题目或者找其他涉及质数筛法的题目。建立知识之间的联系。总结模板与套路将常见的算法写成自己熟悉的“模板”例如二分查找、快速排序、DFS/BFS框架、并查集、Dijkstra算法等。但记住模板是思考的起点不是终点要根据具体问题调整。参加模拟赛与复盘定期参加限时模拟赛锻炼在压力下解题的能力。赛后一定要复盘不仅看错题还要看那些做对了但耗时很长的题思考是否有更优解。算法学习是一场马拉松核心是锻炼逻辑思维和问题解决能力。蓝桥杯是一个很好的舞台但更重要的是通过备赛过程获得实实在在的成长。希望这篇结合具体真题的长文能帮你理清思路在下次遇到问题时能更快地抓住本质写出既正确又优雅的代码。 蓝桥杯算法实战：从去重排序到质数拆分的解题思维与Java实现
1. 从两道真题看蓝桥杯的算法考察逻辑最近在带几个学生准备蓝桥杯发现他们刷题时有个通病拿到题目就埋头写代码结果要么超时要么逻辑漏洞百出。特别是像“质数拆分”和“明明的随机数”这类经典题目看似基础实则暗藏玄机非常能考察一个选手对算法和数据结构的理解深度。今天我就结合这两道题聊聊蓝桥杯Java组解题时除了“能跑通”之外更应该关注的那些东西——比如如何把一道题拆解成清晰的步骤如何选择合适的数据结构以及如何写出既高效又健壮的代码。这不仅仅是应付比赛更是锻炼工程思维的好机会。“质数拆分”本质上是一个动态规划问题但披着数论的外衣你需要先筛出质数再将其视为“物品”进行组合。而“明明的随机数”则是考察对Java集合框架的熟练运用和去重排序的基本功。两道题一难一易组合在一起恰好覆盖了从基础语法到中等难度算法的过渡。接下来我会先带大家吃透“明明的随机数”这道开胃菜建立信心和规范再深入“质数拆分”的核心拆解其动态规划的建模过程。你会发现把思路理清比盲目敲代码要重要得多。2. “明明的随机数”巩固基础与规范编码这道题可以说是蓝桥杯乃至许多OJ平台的“Hello World”级算法题。题目要求很简单输入N个随机整数去重后排序输出。很多新手觉得用Arrays.sort()和一层循环去重就完事了但这样往往只能过样例在性能或边界条件上会栽跟头。我们先从最直接的思路开始逐步优化。2.1 问题重述与输入输出分析题目描述通常为明明生成了N个1到1000之间的随机整数请你删去其中重复的数字并按从小到大的顺序输出。输入有两行第一行是随机整数的个数N第二行是N个用空格隔开的整数。这里有几个关键点需要预先明确这也是很多同学第一次提交就“Wrong Answer”的原因N的范围题目虽未明确但根据经验N可能很大比如10^5。这意味着O(N²)的暴力去重双重循环比较一定会超时。去重与排序的优先级必须先完成去重再对去重后的结果排序。如果先排序再去重在编码上会更简单但逻辑上依然是两个独立步骤。输出格式通常要求每个数字占一行或者用空格隔开在一行内输出务必看清题目要求。一个健壮的程序必须处理这些边界。例如当N0时程序不应该崩溃而应该无输出或输出空行。输入的数字可能不是严格在1-1000之间但只要在int范围内我们的算法就应该能处理。2.2 方案对比从暴力到优雅我们先看看几种常见的实现方案并分析其优劣。方案一排序后遍历去重这是最直观的方法。先使用Arrays.sort()对输入数组进行排序时间复杂度为O(N log N)。排序后相同的数字会相邻。然后遍历数组只输出与上一个输出不同的数字。import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } Arrays.sort(arr); // 处理边界如果数组为空则直接结束 if (n 0) { return; } // 输出第一个元素 System.out.println(arr[0]); for (int i 1; i n; i) { // 如果当前元素不等于前一个元素则输出 if (arr[i] ! arr[i - 1]) { System.out.println(arr[i]); } } } }优点逻辑清晰代码简短利用排序特性自然去重。缺点修改了原始输入数组排序操作如果后续还需要原数组则需拷贝。另外当数字范围已知且较小时有更优解。方案二利用布尔数组标记桶排序思想由于题目限定了数字范围1-1000我们可以利用这个信息。创建一个大小为1001的布尔数组boolean[] flag new boolean[1001]。遍历输入数字以该数字为下标将对应位置标记为true。最后遍历flag数组下标值即为排序去重后的结果。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); boolean[] exists new boolean[1001]; // 下标0-1000 for (int i 0; i n; i) { int num sc.nextInt(); exists[num] true; // 标记该数字存在 } for (int i 1; i 1000; i) { // 题目范围是1-1000 if (exists[i]) { System.out.println(i); } } } }优点时间复杂度为O(NM)其中M是数值范围1001在N很大时效率极高且天然完成了排序和去重。缺点严重依赖于数值范围已知且不大的前提。如果数字范围是整型这种方法会消耗巨大内存约2^31个布尔值不可行。方案三使用TreeSet最符合Java风格的解法TreeSet是Java集合框架中基于红黑树实现的有序集合它自动保证元素唯一且按自然顺序或指定比较器排序。import java.util.Scanner; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); TreeSetInteger set new TreeSet(); for (int i 0; i n; i) { set.add(sc.nextInt()); // 添加操作自动去重TreeSet自动排序 } for (Integer num : set) { System.out.println(num); } } }优点代码极其简洁完全将去重和排序的逻辑委托给TreeSet体现了Java高级API的便捷性。时间复杂度为O(N log N)与排序法相当。缺点对于算法竞赛需要了解其底层是红黑树每次插入是O(log N)。在极端追求性能的场景下可能不如方案二。但绝大多数情况下这是最佳选择。提示在蓝桥杯等竞赛中如果题目明确数值范围小如本题的1-1000方案二桶标记法是首选因为它最快且稳定。如果不确定范围或范围很大方案三TreeSet是最优雅和通用的选择。方案一则是理解基础算法流程的好例子。2.3 常见“坑点”与调试心得即便思路正确实现时也可能踩坑。这里分享几个我学生常犯的错误输入读取问题使用Scanner时在读取完数字后如果下一行还有输入比如字符串要注意用nextLine()吸收掉换行符。本题只有数字问题不大。输出格式问题题目要求每行一个数就不能输出成一行用空格隔开。务必仔细阅读输出描述。有时最后一个数字后面不能有多余空格或换行需要使用StringBuilder进行拼接控制。边界条件处理当N0或1时你的循环还能正常工作吗Arrays.sort()对空数组排序不会报错但后续的arr[0]就会数组越界。方案二的循环从1开始也需要注意N0的情况。性能考量虽然本题数据量可能不大但养成好习惯。避免在循环内进行字符串拼接如s num “\n”因为会创建大量临时对象。使用StringBuilder或直接System.out.println是更好的选择。在实际编码中我建议先写方案三因为它最不容易出错。如果追求极致性能再考虑根据题目条件换用方案二。理解每种方案背后的数据结构数组、红黑树比记住代码更重要。3. “质数拆分”动态规划与数论的结合如果说“明明的随机数”是热身那“质数拆分”就是正餐了。这道题完美地结合了数论质数筛法和动态规划背包问题是蓝桥杯考查综合能力的典型题目。题目通常描述为将某个正整数拆分为若干个不同的质数之和问有多少种拆分方法。例如2019可以被拆分成多少种不同的质数组合看到“拆分”、“多少种方法”有经验的选手立刻会联想到动态规划中的“组合问题”。但这里的“物品”不是题目直接给出的而是需要我们自己先求出来——所有小于目标数的质数。因此解题分为两个清晰的阶段第一阶段筛质数第二阶段动态规划计数。3.1 第一阶段高效筛选质数动态规划需要质数作为“物品”列表。如何快速得到所有小于目标数N的质数这里就需要用到高效的筛法。最著名的有两种埃拉托斯特尼筛法埃氏筛和欧拉筛线性筛。埃氏筛Eratosthenes Sieve原理很简单从2开始将每个质数的倍数标记为合数。public static ListInteger getPrimes(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; // 0和1不是质数 ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); // i是质数 // 标记i的所有倍数为合数 // 优化从i*i开始标记因为小于i*i的合数已被更小的质数标记过 if ((long) i * i limit) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } } return primes; }时间复杂度O(N log log N)对于N2019绰绰有余甚至N10^6也很快。优点实现简单易于理解和记忆。缺点一个合数会被多个质数标记有重复操作。欧拉筛线性筛欧拉筛保证了每个合数只被其最小的质因数标记一次从而达到线性时间复杂度O(N)。public static ListInteger getPrimesLinear(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); } // 用当前已得到的质数 primes.get(j) 去标记合数 for (int j 0; j primes.size() i * primes.get(j) limit; j) { isPrime[i * primes.get(j)] false; // 关键如果i能被当前质数整除则跳出循环 // 保证每个合数只被其最小质因子标记一次 if (i % primes.get(j) 0) { break; } } } return primes; }对于本题N2019两种筛法时间差异微乎其微。但在面对更大数据如N10^7时欧拉筛的优势会体现出来。在竞赛中如果对筛法不熟用埃氏筛足矣代码更不容易写错。注意在动态规划中我们需要的质数列表是primes。同时我们可能还需要快速判断一个数是否为质数这时isPrime布尔数组就派上用场了。在“质数拆分”问题中我们通常只需要列表。3.2 第二阶段动态规划建模与实现拿到质数列表后问题转化为给定一个目标总和S如2019和一系列互不相同的“物品”质数每个物品只能使用一次不同质数求恰好装满容量S的背包有多少种组合方式这是一个经典的0-1背包计数问题。定义状态dp[i][j]为考虑前i个质数组成总和为j的方案数。状态转移方程如下如果不选第i个质数p方案数等于前i-1个质数组成j的方案数即dp[i][j] dp[i-1][j]。如果选第i个质数p前提是j p方案数等于前i-1个质数组成j-p的方案数即dp[i][j] dp[i-1][j-p]。初始化dp[0][0] 1表示用0个质数组成0有1种方案什么都不选。其他dp[0][j] (j0) 0。最终答案dp[n][S]其中n是质数的个数。空间优化滚动数组由于dp[i][j]只依赖于dp[i-1][...]我们可以将二维数组压缩成一维数组dp[j]。但需要注意为了确保每个质数只使用一次内层循环j需要从大到小遍历。public static long countPrimeSplits(int target) { ListInteger primes getPrimes(target); // 获取所有小于等于target的质数 long[] dp new long[target 1]; dp[0] 1; // 初始化总和为0的方案数为1 for (int prime : primes) { // 0-1背包逆序更新 for (int j target; j prime; j--) { dp[j] dp[j - prime]; } } return dp[target]; }为什么内层要逆序这是0-1背包空间优化的关键。如果正序遍历当更新dp[j]时dp[j - prime]可能已经在同一轮考虑当前质数时被更新过了这意味着我们可能重复使用了当前质数多次变成了“完全背包”问题。逆序遍历保证了在更新dp[j]时dp[j - prime]还是基于“未考虑当前质数”的状态从而每个质数最多被使用一次。3.3 完整代码实现与测试将两部分结合起来并处理输入输出完整的解题代码如下import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int target sc.nextInt(); // 例如输入 2019 System.out.println(countPrimeSplits(target)); } // 埃氏筛获取质数列表 public static ListInteger getPrimes(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); if ((long) i * i limit) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } } return primes; } // 动态规划计算拆分方案数 public static long countPrimeSplits(int target) { ListInteger primes getPrimes(target); long[] dp new long[target 1]; dp[0] 1; for (int prime : primes) { for (int j target; j prime; j--) { dp[j] dp[j - prime]; } } return dp[target]; } }测试与验证输入7质数有[2,3,5,7]。拆分方式有7, 25, 223? (不行2重复了)。实际上77, 25。答案是2。程序输出2。输入10质数[2,3,5,7]。拆分23510, 3710, 22...不允许重复。答案是2。程序输出2。输入2019这是一个较大的数需要程序有较好的效率。运行上述代码可以很快得到结果具体数值需运行程序。3.4 深入思考不同与重复的边界这道题有一个非常关键的约束“不同的质数”。这直接决定了我们使用0-1背包模型。如果题目改为“可重复使用同一个质数”那就变成了完全背包计数问题其动态规划的内层循环就需要正序遍历了。// 假设质数可以重复使用完全背包问题 public static long countPrimeSplitsUnlimited(int target) { ListInteger primes getPrimes(target); long[] dp new long[target 1]; dp[0] 1; for (int prime : primes) { // 完全背包正序更新 for (int j prime; j target; j) { dp[j] dp[j - prime]; } } return dp[target]; }仅仅是一个遍历顺序的区别问题的本质就变了。在比赛时一定要像这样仔细审题抓住“不同”、“重复”、“顺序有关/无关”这些关键词它们直接决定了算法模型的选择。另一个容易混淆的点是“组合”与“排列”。本题是组合问题235和325被视为同一种所以我们的物品质数是放在外层循环的。如果是排列问题顺序不同视为不同方案则需要把目标总和放在外层循环物品放在内层。理解这些细微差别才能灵活应对变种题目。4. 算法竞赛中的实战技巧与心态通过这两道题我们不仅学习了具体解法更重要的是一种系统化的解题思维。在蓝桥杯或任何算法竞赛中时间有限压力大如何快速且正确地解决问题我结合自己的参赛和教学经验分享几点心得。4.1 四步解题法读、析、设、码读题与抽象5分钟这是最关键的一步。逐字逐句读题用笔划出关键约束数据范围N, M的大小、特殊条件是否重复、是否有序、输入输出格式。像“质数拆分”中的“不同质数”就是核心约束。将实际问题抽象成数学模型或已知算法问题背包、搜索、图论等。复杂度分析与算法设计5-10分钟根据数据范围反推可接受的算法复杂度。例如N≤20可能用指数级搜索N≤1000可能用O(N²)动态规划N≤10^5通常需要O(N log N)或O(N)的算法。设计算法步骤在草稿纸上画出状态转移或流程。细节设计与边界考虑5分钟设计数据结构用数组还是集合确定循环边界思考初始化状态。考虑极端情况空输入、最大/最小输入、结果为0或1的情况。为这些情况设计测试样例。编码与调试剩余时间将设计翻译成代码。优先保证代码清晰可读使用有意义的变量名。写完后用自己设计的边界样例和题目样例进行测试。如果出错使用打印语句或调试器定位问题是算法逻辑错误还是边界处理不当很多同学把大部分时间花在编码和调试上往往是因为前两步没做好。磨刀不误砍柴工清晰的思路能节省大量时间。4.2 Java选手的武器库与避坑指南作为Java选手我们有一些独特的优势和需要特别注意的“坑”。优势武器库丰富的集合框架ArrayList,LinkedList,HashSet,TreeSet,HashMap,PriorityQueue等。像“明明的随机数”用TreeSet复杂去重计数用HashMap能极大简化代码。强大的工具类Arrays.sort(),Collections.sort(),Math类下的各种函数。StringBuilder在需要频繁拼接字符串时如输出结果务必使用StringBuilder直接使用连接在循环中会带来巨大的性能开销。常见“坑点”输入输出效率当输入数据量极大10^5以上时Scanner可能会成为性能瓶颈。此时应换用BufferedReader。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String[] params br.readLine().split( ); int n Integer.parseInt(params[0]);整数溢出这是最隐蔽的Bug之一两个int相乘即使结果用long接收乘法运算本身也可能已经溢出。例如计算i * i时如果i接近10^5i*i就超过int范围了。解决办法是提前将操作数转为long(long) i * i。在“质数拆分”的dp计数中方案数也可能超过int范围所以dp数组要用long。递归深度Java默认的栈深度可能无法支持很深的递归如DFS搜索深度超过1万层。非尾递归的深搜要考虑用栈数据结构手动模拟或者尝试迭代解法。内存限制蓝桥杯通常内存限制为128MB或256MB。要估算数组大小例如一个int[100000][100000]的二维数组绝对会内存超限。在必须使用二维DP时考虑是否能滚动数组优化成一维。4.3 从刷题到精通如何有效练习最后谈谈练习方法。盲目刷几百道题不如精做几十道。一题多解就像我们对“明明的随机数”做的尝试用多种方法解决同一问题并分析时空复杂度差异。这能加深你对数据结构和算法的理解。举一反三做完“质数拆分”可以去找其他背包问题01背包、完全背包、多重背包的题目或者找其他涉及质数筛法的题目。建立知识之间的联系。总结模板与套路将常见的算法写成自己熟悉的“模板”例如二分查找、快速排序、DFS/BFS框架、并查集、Dijkstra算法等。但记住模板是思考的起点不是终点要根据具体问题调整。参加模拟赛与复盘定期参加限时模拟赛锻炼在压力下解题的能力。赛后一定要复盘不仅看错题还要看那些做对了但耗时很长的题思考是否有更优解。算法学习是一场马拉松核心是锻炼逻辑思维和问题解决能力。蓝桥杯是一个很好的舞台但更重要的是通过备赛过程获得实实在在的成长。希望这篇结合具体真题的长文能帮你理清思路在下次遇到问题时能更快地抓住本质写出既正确又优雅的代码。