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

最近在准备蓝桥杯竞赛的同学经常会遇到两类经典问题：质数相关计算和位运算应用。今天我就结合两道典型题目，分享一下我的解题思路和优化技巧。这两道题都来自第十六届蓝桥杯Java B组，分别是第三题和第四题，涉及集合操作、质数筛法和异或运算等核心知识点。

2. 两数之和为质数问题解析

2.1 问题描述与输入输出

给定两个整数数组a和b，长度分别为n和m。要求统计所有满足a[i] + b[j]为质数的不同组合的数量，其中质数的范围不超过n+m。

输入格式：

• 第一行两个整数n, m
• 第二行n个整数表示数组a
• 第三行m个整数表示数组b

输出格式：

• 一个整数表示满足条件的不同的质数和的数量

示例： 输入： 3 4 2 1 3 4 5 6 7 输出： 3

2.2 解题思路与算法选择

这道题的核心在于高效判断两个数之和是否为质数。直接思路是双重循环遍历所有a[i]+b[j]组合，然后对每个和进行质数判断。但这种朴素方法的时间复杂度是O(n×m×√S)，当n和m较大时（比如都达到10^5），这种解法显然会超时。

更优的解决方案是：

1. 预处理出所有可能的质数（使用埃拉托斯特尼筛法）
2. 使用HashSet存储质数实现O(1)查询
3. 遍历所有a[i]+b[j]组合，用HashSet快速判断是否为质数

这种优化将时间复杂度降为O(n×m)，空间复杂度为O(S)，其中S是n+m的最大值。

2.3 埃拉托斯特尼筛法实现

埃氏筛是解决质数判定问题的经典算法，其核心思想是从小到大枚举每个数，如果当前数未被标记为非质数，则它是质数，并标记它的所有倍数为非质数。

Set<Integer> sieveOfEratosthenes(int max) { Set<Integer> 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²开始而不是2i

2.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; // 预处理质数集合 Set<Integer> 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(); } Set<Integer> 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 性能优化与注意事项

1. 输入规模考虑：当n和m较大时（如10^5），双重循环的O(n×m)复杂度仍然可能超时。这时需要考虑更优的算法，如先统计数字频率，再组合计算。

2. 质数筛法选择：对于更大的数据范围（如10^7以上），埃氏筛可能空间不足，可以考虑欧拉筛（线性筛）。

3. 边界条件处理：

   • 注意1不是质数
   • 和为2的情况需要特殊处理（因为2是唯一的偶质数）
   • 输入数字可能为负数，需要额外判断

4. 集合选择：使用HashSet而不是TreeSet，因为前者查询时间复杂度为O(1)，后者为O(log n)。

提示：在竞赛中，当遇到质数相关问题时，预处理质数表往往是关键优化点。提前计算好质数可以大幅减少运行时的计算量。

3. 电池分组异或问题解析

3.1 问题描述与异或性质

给定一个整数数组，要求判断是否能将其分成两个非空子集，使得两个子集的异或和相等。

异或（XOR）的重要性质：

1. 交换律：a ^ b = b ^ a
2. 结合律：(a ^ b) ^ c = a ^ (b ^ c)
3. 自反性：a ^ a = 0
4. 恒等性：a ^ 0 = a

3.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
• 否则，输出NO

3.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 特殊情况分析与验证

1. 数组长度为2：必须两个数相等才能分组，此时异或和确实为0。

2. 所有元素相同：

   • 如果元素个数为偶数，可以平分
   • 如果为奇数，异或和不为0（除非元素本身就是0）

3. 包含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 → YES

3.5 扩展思考：找出具体分组方案

虽然题目只要求判断可行性，但我们可以进一步思考如何找到具体的分组方案。当total = 0时，任何非空真子集的异或和X，其补集的异或和必然也是X。因此可以：

1. 计算前缀异或和
2. 找到第一个位置i使得prefixXor[i]等于任意X
3. 前i个元素为一组，其余为另一组

// 扩展：找出一个可行的分组方案 List<Integer> 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)) { List<Integer> group = new ArrayList<>(); for (int j = 0; j <= i; j++) { group.add(arr[j]); } return group; } } return null; }

4. 竞赛编程技巧与常见问题

4.1 质数相关问题优化技巧

1. 预处理质数表：在程序开始时一次性计算出可能用到的所有质数，避免重复计算。

2. 质数判定优化：

   • 试除法只需检查到√n
   • 排除偶数（除2外）
   • 使用6k±1优化（所有大于3的质数都可以表示为6k±1）

3. 质因数分解：结合筛法预处理最小质因子，可以快速分解任意数的质因数。

4.2 位运算技巧总结

1. 异或性质应用：

   • 交换两个数：a ^= b; b ^= a; a ^= b;
   • 找出只出现一次的数字（其他都出现两次）
   • 不使用临时变量交换值

2. 常用位操作：

   • 判断奇偶：n & 1
   • 取最低位的1：n & -n
   • 清除最低位的1：n & (n - 1)

3. 状态压缩：使用整数的二进制位表示集合，可以高效处理子集、组合等问题。

4.3 Java集合类的选择与性能

1. HashSet vs TreeSet：

   • HashSet：基于哈希表，O(1)查询，无序
   • TreeSet：基于红黑树，O(log n)查询，有序

2. ArrayList vs LinkedList：

   • ArrayList：随机访问快，O(1)；插入删除慢，O(n)
   • LinkedList：随机访问慢，O(n)；插入删除快，O(1)

3. HashMap优化：

   • 预设初始容量避免扩容
   • 使用包装类型时注意自动装箱开销

4.4 竞赛中的输入输出优化

1. 使用BufferedReader代替Scanner：

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken());

2. 输出大量数据时使用StringBuilder：

StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append(result[i]).append(" "); } System.out.println(sb.toString().trim());

3. 关闭同步提升速度（仅C++）：

ios::sync_with_stdio(false); cin.tie(nullptr);

4.5 调试与测试技巧

1. 边界测试：

   • 空输入
   • 单个元素
   • 最大值/最小值边界

2. 随机测试数据生成：

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); }

3. 断言调试：

assert totalXor == 0 : "Total XOR should be zero for valid partition";

在实际竞赛中，我通常会先写出朴素解法确保正确性，然后再逐步优化。对于质数相关问题，预处理是关键；而对于位运算问题，深入理解其性质往往能发现巧妙的解法。这两道题虽然看似简单，但包含了算法竞赛中许多核心思想，值得反复练习和思考。