蓝桥杯Java解题：质数判定与异或分组实战

1. 蓝桥杯Java B组解题实战质数判定与异或分组最近在准备蓝桥杯竞赛的同学经常会遇到两类经典问题质数相关计算和位运算应用。今天我就结合两道典型题目分享一下我的解题思路和优化技巧。这两道题都来自第十六届蓝桥杯Java B组分别是第三题和第四题涉及集合操作、质数筛法和异或运算等核心知识点。2. 两数之和为质数问题解析2.1 问题描述与输入输出给定两个整数数组a和b长度分别为n和m。要求统计所有满足a[i] b[j]为质数的不同组合的数量其中质数的范围不超过nm。输入格式第一行两个整数n, m第二行n个整数表示数组a第三行m个整数表示数组b输出格式一个整数表示满足条件的不同的质数和的数量示例 输入 3 4 2 1 3 4 5 6 7 输出 32.2 解题思路与算法选择这道题的核心在于高效判断两个数之和是否为质数。直接思路是双重循环遍历所有a[i]b[j]组合然后对每个和进行质数判断。但这种朴素方法的时间复杂度是O(n×m×√S)当n和m较大时比如都达到10^5这种解法显然会超时。更优的解决方案是预处理出所有可能的质数使用埃拉托斯特尼筛法使用HashSet存储质数实现O(1)查询遍历所有a[i]b[j]组合用HashSet快速判断是否为质数这种优化将时间复杂度降为O(n×m)空间复杂度为O(S)其中S是nm的最大值。2.3 埃拉托斯特尼筛法实现埃氏筛是解决质数判定问题的经典算法其核心思想是从小到大枚举每个数如果当前数未被标记为非质数则它是质数并标记它的所有倍数为非质数。SetInteger sieveOfEratosthenes(int max) { SetInteger primes new HashSet(); boolean[] isComposite new boolean[max 1]; for (int i 2; i max; i) { if (!isComposite[i]) { primes.add(i); for (int j i * 2; j max; j i) { isComposite[j] true; } } } return primes; }在实际编码中我们可以进一步优化外层循环只需遍历到√max内层循环可以从i²开始而不是2i2.4 完整代码实现与注释import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class PrimeSumPairs { public static void main(String[] args) { Scanner scan new Scanner(System.in); int n scan.nextInt(); int m scan.nextInt(); int maxSum n m; // 预处理质数集合 SetInteger primes new HashSet(); boolean[] isComposite new boolean[maxSum 1]; for (int i 2; i maxSum; i) { if (!isComposite[i]) { primes.add(i); for (int j i * 2; j maxSum; j i) { isComposite[j] true; } } } int[] a new int[n]; int[] b new int[m]; for (int i 0; i n; i) { a[i] scan.nextInt(); } for (int i 0; i m; i) { b[i] scan.nextInt(); } SetInteger validSums new HashSet(); for (int numA : a) { for (int numB : b) { int sum numA numB; if (primes.contains(sum)) { validSums.add(sum); } } } System.out.println(validSums.size()); scan.close(); } }2.5 性能优化与注意事项输入规模考虑当n和m较大时如10^5双重循环的O(n×m)复杂度仍然可能超时。这时需要考虑更优的算法如先统计数字频率再组合计算。质数筛法选择对于更大的数据范围如10^7以上埃氏筛可能空间不足可以考虑欧拉筛线性筛。边界条件处理注意1不是质数和为2的情况需要特殊处理因为2是唯一的偶质数输入数字可能为负数需要额外判断集合选择使用HashSet而不是TreeSet因为前者查询时间复杂度为O(1)后者为O(log n)。提示在竞赛中当遇到质数相关问题时预处理质数表往往是关键优化点。提前计算好质数可以大幅减少运行时的计算量。3. 电池分组异或问题解析3.1 问题描述与异或性质给定一个整数数组要求判断是否能将其分成两个非空子集使得两个子集的异或和相等。异或XOR的重要性质交换律a ^ b b ^ a结合律(a ^ b) ^ c a ^ (b ^ c)自反性a ^ a 0恒等性a ^ 0 a3.2 数学推导与解题思路设总异或和为total两个子集的异或和分别为X和Y。根据题意有 X Y 根据异或性质 total X ^ Y X ^ X 0反过来如果total 0那么任意一个子集的异或和X另一个子集的异或和Y X ^ total X ^ 0 X即总能找到满足条件的分组。因此问题简化为判断整个数组的异或和是否为0如果total 0输出YES否则输出NO3.3 完整代码实现import java.util.Scanner; public class XorPartition { public static void main(String[] args) { Scanner scan new Scanner(System.in); int n scan.nextInt(); int[] batteries new int[n]; int totalXor 0; for (int i 0; i n; i) { batteries[i] scan.nextInt(); totalXor ^ batteries[i]; } System.out.println(totalXor 0 ? YES : NO); scan.close(); } }3.4 特殊情况分析与验证数组长度为2必须两个数相等才能分组此时异或和确实为0。所有元素相同如果元素个数为偶数可以平分如果为奇数异或和不为0除非元素本身就是0包含0的情况0不影响异或结果可以灵活分配。验证示例 输入3 1 2 3 计算3 ^ 1 ^ 2 ^ 3 (3 ^ 3) ^ (1 ^ 2) 0 ^ 3 3 ≠ 0 → NO输入4 1 2 3 0 计算1 ^ 2 ^ 3 ^ 0 0 → YES3.5 扩展思考找出具体分组方案虽然题目只要求判断可行性但我们可以进一步思考如何找到具体的分组方案。当total 0时任何非空真子集的异或和X其补集的异或和必然也是X。因此可以计算前缀异或和找到第一个位置i使得prefixXor[i]等于任意X前i个元素为一组其余为另一组// 扩展找出一个可行的分组方案 ListInteger findPartition(int[] arr) { int total 0; for (int num : arr) total ^ num; if (total ! 0) return null; int prefix 0; for (int i 0; i arr.length; i) { prefix ^ arr[i]; if (prefix (total ^ prefix)) { ListInteger group new ArrayList(); for (int j 0; j i; j) { group.add(arr[j]); } return group; } } return null; }4. 竞赛编程技巧与常见问题4.1 质数相关问题优化技巧预处理质数表在程序开始时一次性计算出可能用到的所有质数避免重复计算。质数判定优化试除法只需检查到√n排除偶数除2外使用6k±1优化所有大于3的质数都可以表示为6k±1质因数分解结合筛法预处理最小质因子可以快速分解任意数的质因数。4.2 位运算技巧总结异或性质应用交换两个数a ^ b; b ^ a; a ^ b;找出只出现一次的数字其他都出现两次不使用临时变量交换值常用位操作判断奇偶n 1取最低位的1n -n清除最低位的1n (n - 1)状态压缩使用整数的二进制位表示集合可以高效处理子集、组合等问题。4.3 Java集合类的选择与性能HashSet vs TreeSetHashSet基于哈希表O(1)查询无序TreeSet基于红黑树O(log n)查询有序ArrayList vs LinkedListArrayList随机访问快O(1)插入删除慢O(n)LinkedList随机访问慢O(n)插入删除快O(1)HashMap优化预设初始容量避免扩容使用包装类型时注意自动装箱开销4.4 竞赛中的输入输出优化使用BufferedReader代替ScannerBufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken());输出大量数据时使用StringBuilderStringBuilder sb new StringBuilder(); for (int i 0; i n; i) { sb.append(result[i]).append( ); } System.out.println(sb.toString().trim());关闭同步提升速度仅Cios::sync_with_stdio(false); cin.tie(nullptr);4.5 调试与测试技巧边界测试空输入单个元素最大值/最小值边界随机测试数据生成Random random new Random(); int n random.nextInt(100) 1; int[] arr new int[n]; for (int i 0; i n; i) { arr[i] random.nextInt(1000); }断言调试assert totalXor 0 : Total XOR should be zero for valid partition;在实际竞赛中我通常会先写出朴素解法确保正确性然后再逐步优化。对于质数相关问题预处理是关键而对于位运算问题深入理解其性质往往能发现巧妙的解法。这两道题虽然看似简单但包含了算法竞赛中许多核心思想值得反复练习和思考。