第十六届蓝桥杯大赛软件赛省赛Java 大学 B 组
题目链接：
Q1：逃离高塔（简单）
Q2：消失的蓝宝（简单）
Q3：电池分组（简单）
Q4：魔法科考试（简单）
算法原理：
Q1解法：暴力枚举
时间复杂度O(1)
思路很简单，暴力枚举每个数，取出个位判断是否为3，但是这里有个小细节，就是如果只是简单相乘会导致int溢出，因此我们需要转成long类型，然后用long来存储
Q2解法：解方程组
时间复杂度O(1)
这第二题有点刁钻了，因为暴力枚举会超时，本质原因在于从1开始枚举，数量太大了，因此我们通过方程组消参的方式来求出整数N
(N+20250412)=a*20240413
(N+20240413)=b*20250412
20250412-20240413=a*20240413-b*20250412
(a+1)*20240413=(b+1)*20250412
代值解得a=20250411
因此可直接输出N=20250411L×20240413L－20250412LQ3解法：异或消消乐
时间复杂度O(T·N)
看上去好像比较麻烦，但其实很简单
根据“异或消消乐”的原理，两个数相同，那么它们的异或值必然为0，那么如果两组电池的异或和相同，那么这两组的异或和再进行一次异或，值必然为0，因此我们只需将T个测试用例的各个N个数异或再一起，分别判断总的异或和是否为0即可，为0就打印YES，否则打印NOQ4
解法一：暴力枚举（通过率76.2%，存在超时）
时间复杂度O(n·m·√(n+m))
思路很简单，就是组合任意两个数a和b，在a+b≤m+n时，a+b是个质数，就累加一次，但需要注意，这里的质数的数量要去重，由此我们想到暴力枚举每个a和b的组合，只要符合条件就扔Set里去重，最后返回Set的大小即可，但由于时间复杂度太大，导致部分测试用例超时，通过率仅有76.2%
解法二：埃氏筛（通过率100%）
时间复杂度O (n・m)
之前用过埃氏筛的题目👇
第 479 场周赛Q2——3770. 可表示为连续质数和的最大质数
①为了避免每次判断 “S 是否为质数” 都重复计算（比如之前的islegal函数每次要遍历√x），先提前筛选出n+m 范围内的所有质数，后续判断只需 O (1) 时间：
②初始化质数数组：创建布尔数组isPrime，长度为n+m+1用于覆盖所有可能的 S 值，先将2~n+m的位置设为true，默认这些数是质数
③筛法核心逻辑：
从 2 到 n+m遍历每个数 i
若 i 是质数，则把i的平方开始的所有倍数（i*i, i*i+i, i*i+2i...）标记为false，因为如果 i 是质数，那么 i 的所有倍数都不是质数
④关键去重：为保证每个 S 只算 1 次，若满足条件，计数cnt++，并立即将isPrime[S]设为false
Java代码：
Q1
import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); //在此输入您的代码... int cnt=0; for(int i=1;i<=2025;i++){ long sum=1L*i*i*i; if(sum%10==3) cnt++; } System.out.println(cnt); scan.close(); } }Q2
import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); //(N+20250412)=a*20240413 //(N+20240413)=b*20250412 //20250412-20240413=a*20240413-b*20250412 //(a+1)*20240413=(b+1)*20250412 //a=20250411 System.out.println(20250411L*20240413L-20250412L); scan.close(); } }Q3
import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //在此输入您的代码... //获取测试用例数量T int T=sc.nextInt(); for(int i=0;i<T;i++){ //获取此次测试用例的电池总数 int N=sc.nextInt(); int t=0; for(int j=0;j<N;j++){ t^=sc.nextInt(); } if(t==0) System.out.println("YES"); else System.out.println("NO"); } sc.close(); } }Q4
import java.lang.Math; import java.util.*; public class Main { //解法一：暴力枚举（部分测试用例存在超时） public static void main(String[] args) { Scanner sc = new Scanner(System.in); Set<Integer> hash=new HashSet<>(); int n=sc.nextInt(); int[] a=new int[n]; int m=sc.nextInt(); int[] b=new int[m]; for(int i=0;i<n;i++) a[i]=sc.nextInt(); for(int i=0;i<m;i++) b[i]=sc.nextInt(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i]+b[j]<=n+m&&islegal(a[i]+b[j])) hash.add(a[i]+b[j]); } } System.out.println(hash.size()); sc.close(); } //判断是否为质数 private static boolean islegal(int x){ if(x<=1) return false; for(int i=2;i<=Math.sqrt(x);i++) if(x%i==0) return false; return true; } }import java.lang.Math; import java.util.*; public class Main { //解法二：埃氏筛 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int[] a=new int[n]; int m=sc.nextInt(); int[] b=new int[m]; int cnt=0; //埃氏筛 boolean[] isPrime=new boolean[m+n+1]; for(int i=2;i<=m+n;i++) isPrime[i]=true; for(int i=2;i<=n+m;i++){ if(isPrime[i]){ for(int j=i*i;j<=m+n;j+=i) isPrime[j]=false; } } for(int i=0;i<n;i++) a[i]=sc.nextInt(); for(int i=0;i<m;i++) b[i]=sc.nextInt(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i]+b[j]<=n+m&&isPrime[a[i]+b[j]]){ cnt++; isPrime[a[i]+b[j]]=false; } } } System.out.println(cnt); sc.close(); } }