2.5.第十六届蓝桥杯大赛软件赛省赛Java 大学 B 组(上)

1.逃离高塔问题描述小蓝一觉醒来小蓝被困在一座高耸的塔中。这座塔共有 20252025 层每一层都刻有一个数字的立方值从底层的 1313、2323、3333、⋯⋯一直到顶层的 2025320253层层叠叠直入云霄。塔顶有一扇门门旁刻着一行字“若想离开此塔需找出这些立方数中个位数字为 33 的数的个数。”小蓝非常着急因为他需要尽快离开这座塔去参加即将到来的蓝桥杯比赛。时间紧迫请你帮助他解答这个问题。参考代码package practice4; public class Test4 { public static void main(String[] args) { //1.定义变量统计个数 int sum0; //2.循环判断符合要求的数 for (int i 1; i 2025; i) { //3.求出立方数 /*注意2025的立方非常大要用long存储*/ long result (long) Math.pow(i, 3); //4.判断个位数是否为3 if(result%103) sum; } //5.输出 System.out.println(sum); } }当然了经验丰富的小伙伴会知道立方后个位数为3的数个位只能为7根据这个不需要代码就能推出来。2.消失的蓝宝问题描述“蓝宝又不见了” 2025 年 4 月 12 日蓝桥杯吉祥物“蓝宝”在省赛前夕突然失踪。小蓝翻阅了蓝宝的活动记录发现它的出现时间似乎与蓝桥杯的两个重要日期密切相关第十六届省赛日期 2025041220250412第十五届省赛日期 2024041320240413。经过分析小蓝推测蓝宝的下一次出现时间 NN 满足以下条件N20250412N20250412 能被 2024041320240413 整除。N20240413N20240413 能被 2025041220250412 整除。现在请你帮小蓝找出满足条件的最小正整数 NN预测蓝宝的下一次出现时间。参考代码package practice6; public class Test { public static void main(String[] args) { //1.记录变量 int num1 20250412; int num2 20240413; //2.暴力枚举 for (long i 2 ;i10000000000000L;i){ //i从1开始n会有负数 //3.先根据第一个条件确定n再判断n是否符合第二个条件 long n num2*i - num1; //4.判断 if ((nnum2)%num10){ System.out.println(n); break; } } } }另一种思路设n2025041220240413a,n2024041320250412b,则20240413*(a1)20250412*(b1),又因为20240413和20250412互质所以a1最小为20250412则n20240413*a-2025041220250411 * 20240413 - 20250412。3.电池分组问题描述研究员小蓝受到实验室主任的指示需要对实验室新研发的 n 个新型能量电池进行分组实验。这 N 个能量电池的能量值分别用 A1,A2,…,AN表示每个能量值都是一个整数。为了保证实验的安全性小蓝需要将这 N 个能量电池分成两组使得这两组能量电池的能量值异或和相等。能量值的异或和计算方法如下对于一个集合 S其异或和等于集合中所有元素的按位异或结果。例如集合 {1,2,3} 的异或和为 1⊕2⊕30其中 ⊕ 表示异或运算。现在小蓝想知道这 n个能量电池能否分成两组使得这两组能量电池的能量值异或和相等。注意每组至少包含一个能量电池。请你帮帮他输入格式输入的第一行包含一个整数 T 表示测试用例的数量。每个测试用例占两行第一行包含一个整数 N表示能量电池的数量。第二行包含 n 个整数 A1,A2,…,AN​表示每个能量电池的能量值。输出格式对于每个测试用例输出一行。如果可以将能量电池分成两组使得这两组能量电池的能量值异或和相等则输出YES否则输出NO。样例输入2 3 1 2 3 4 1 2 3 4样例输出YES NO解题思路先假设条件成立能分为两个异或和相等的组那么此时两组的异或和为0。也就意味着只要所有数据的异或和为0就可以将其划分为异或和相等的两组数据.其中不是两组的异或和各自“必须为 0”而是当两组异或和相等时总异或和一定为 0所以要把集合中的所有元素都异或起来看是否为0反过来当总异或和为 0 时两组的异或和必然相等可以是任意值比如 1、3、5 等等。参考代码package practice4; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scannew Scanner(System.in); //1.输入集合个数 int num scan.nextInt(); //2.判断能否分组 /*根据题意只有集合的所有数据经过异或运算后结果为0才能分成两组 * 只要有一个为1就说明存在不符合题意的*/ while (num0){ //定义变量记录异或结果 long result0; //1.输入集合元素个数 int len scan.nextInt(); //2.循环输入集合元素的数据并进行异或运算 for (int i 0; i len; i) { int data scan.nextInt(); result result ^ data; } //3.判断 if(result0) System.out.println(YES); else System.out.println(NO); //4.开始下一个集合判断 num--; } } }4.魔法科考试问题描述小明正在参加魔法科的期末考试考生需要根据给定的口诀组合出有效的魔法。其中老师给定了 n 个上半部分口诀 a1,a2,…,ana1​,a2​,…,an​ 和 m 个下半部分口诀 b1,b2,…,bmb1​,b2​,…,bm​均用整数表示。完整的口诀包含一个上半部分口诀和一个下半部分口诀当选用两个口诀 ai和 bj将组合出完整口诀 Saibj​。当 S满足 S≤nm 且 S 为质数时魔法是有效的。魔法的种类只和 S 的大小有关。如果每个上半部分口诀和每个下半部分口诀在不同的组合中可以重复使用小明想知道一共可能组合出多少种不同的有效魔法输入格式输入共三行。第一行为两个正整数 n,m。第二行为 nn 个由空格分开的正整数 a1,a2,…,an。第三行为 mm 个由空格分开的正整数 b1,b2,…,bm​。输出格式输出共 1行一个整数表示答案。样例输入3 4 2 3 10 3 4 5 1样例输出3样例说明可以组合出 3,5,7 这三个有效魔法。注意事项本体要注意的是质数判断以及有效魔法的不重复性。参考代码不严谨的代码package practice5; import java.util.HashSet; import java.util.Scanner; public class Test { public static void main(String[] args) { Scanner scannew Scanner(System.in); //1.分别输入两个数组长度 int len1scan.nextInt(); int len2scan.nextInt(); //2.分别定义两个数组并录入数据 int[] anew int[len1]; for (int i 0; i len1; i) { a[i]scan.nextInt(); } int[] bnew int[len2]; for (int i 0; i len2; i) { b[i] scan.nextInt(); } //3.判断 HashSetInteger resultnew HashSet(); for (int i 0; i a.length; i) { for (int j 0; j b.length; j) { if( a[i]b[j]len1len2 method(a[i]b[j])){ result.add(a[i]b[j]); } } } //4.输出 System.out.println(result.size()); } //定义一个函数判断当前数是否为质数 private static boolean method(int number){ double tempMath.sqrt(number); int top (int) Math.ceil(temp); //开根号后向上取整 for (int i 2; i top; i) { if(number%i0) return false; //不是质数 } //此时就是质数 return true; } }严谨的代码以及上述代码的漏洞解读a、先分析判断质数方法的问题质数判断函数method()存在两个关键错误会导致结果不准确未处理小于 2 的数质数的定义是「大于 1 的自然数只能被 1 和自身整除」但代码没有判断number 1的情况会把1、0、负数错误判定为质数。向上取整多余且可能出错Math.ceil(Math.sqrt(number))会导致循环多执行一次比如number4sqrt(4)2ceil 后还是 2没问题但number5sqrt(5)≈2.236ceil 后是 3实际只需要循环到 2 即可正确做法是直接取整后循环或用i*i number避免浮点运算。b、代码优化方案提速 修正优化核心思路修正质数判断逻辑补全边界条件去掉多余的浮点运算减少循环次数。减少重复计算提前计算len1len2的值无需每次循环都计算。减少无效循环在两数相加时若和超过len1len2直接跳过提前剪枝。质数判断提速偶数直接排除除了 2循环步长改为 2减少一半循环次数。优化后的完整代码:package practice5; import java.util.HashSet; import java.util.Scanner; public class Test { public static void main(String[] args) { Scanner scan new Scanner(System.in); // 1. 输入数组长度 int len1 scan.nextInt(); int len2 scan.nextInt(); // 2. 录入数组数据 int[] a new int[len1]; for (int i 0; i len1; i) { a[i] scan.nextInt(); } int[] b new int[len2]; for (int i 0; i len2; i) { b[i] scan.nextInt(); } scan.close(); // 关闭Scanner释放资源 //边界防护数组为空的情况 if(len10||len20){ System.out.println(0); return; } // 3. 核心逻辑提前计算总和阈值避免重复计算 int sumThreshold len1 len2; HashSetInteger result new HashSet(); for (int numA : a) { // 增强for循环可读性更高 for (int numB : b) { int sum numA numB; // 提前剪枝和超过阈值直接跳过减少质数判断的调用 if (sum sumThreshold) { continue; } // 调用优化后的质数判断方法 if (isPrime(sum)) { result.add(sum); } } } // 4. 输出结果 System.out.println(result.size()); } /** * 优化后的质数判断方法 * 1. 处理边界小于2不是质数2是唯一偶质数 * 2. 排除偶数减少一半循环次数 * 3. 用i*i number替代sqrt避免浮点运算误差 */ private static boolean isPrime(int number) { // 边界1小于2的数不是质数 if (number 1) { return false; } // 边界22是唯一的偶质数 if (number 2) { return true; } // 边界3偶数且大于2不是质数 if (number % 2 0) { return false; } //此时该数必定为奇数那么如果不是质数那么因数必定不是偶数 // 核心循环只判断奇数从3开始步长2到sqrt(number)为止 for (int i 3; i * i number; i 2) { if (number % i 0) { return false; } } return true; } }c、关键优化点解释优化点原代码问题优化后效果质数判断边界处理未处理 number1错误判定非质数结果准确避免无效循环排除偶数 步长 2循环遍历所有数效率低循环次数减少 50%大幅提速i*i number用 sqrtceil浮点运算有误差且耗时整数运算更高效无精度问题提前计算 sumThreshold每次循环都计算 len1len2重复运算只计算 1 次减少冗余计算提前剪枝 sum 阈值无效调用质数判断方法减少不必要的质数判断节省时间增强 for 循环普通 for 循环可读性差代码更简洁无性能损耗关闭 Scanner未关闭资源可能导致内存泄漏资源释放更规范尤其大数据量时更稳定d、额外提速建议针对大数据量如果输入的数组长度很大比如 len1、len2 都是 10^4 级别可以再做以下优化预缓存质数提前计算0~(len1len2)范围内的所有质数用埃氏筛 / 欧拉筛后续直接查表避免重复判断质数。示例埃氏筛优化// 在main方法中提前生成质数缓存 int maxNum len1 len2; boolean[] isPrimeCache new boolean[maxNum 1]; // 初始化埃氏筛 for (int i 2; i maxNum; i) { isPrimeCache[i] true; } for (int i 2; i * i maxNum; i) { if (isPrimeCache[i]) { for (int j i * i; j maxNum; j i) { isPrimeCache[j] false; } } } // 后续判断时直接用if (isPrimeCache[sum])替换 HashSet如果不需要去重题目中 sum 可能重复HashSet 是必要的但可以用布尔数组替代 HashSet查询更快。e.总结质数判断核心修正必须处理number1和偶数用i*i number替代浮点运算结果才准确且高效。性能优化关键提前剪枝sum 超过阈值直接跳过、排除偶数循环、减少重复计算能让代码运行速率提升 50% 以上。大数据量进阶埃氏筛预缓存质数是最优方案避免多次重复判断同一个数是否为质数。d.关于判断是否为质数的方法中for循环中不判断偶数的原因不是 “不判断偶数”而是 “提前判断偶数并直接排除”这是质数判断里最经典的提速技巧我把这个逻辑拆透质数的定义是大于 1 的自然数只能被 1 和自身整除除了数字 2 之外所有偶数都不可能是质数-原因很简单偶数的定义是 “能被 2 整除的数”除了 2 之外所有偶数都至少有 3 个因数1、2、自身违反质数的定义2是唯一的偶质数提前判断偶数” 的核心答案减少无效循环无精度风险