第十六届蓝桥杯大赛软件赛省赛Java 大学 A 组
题目链接：
Q1：数位倍数（简单）
Q2：2025（简单）
Q3：变换数组（简单）
Q4：最短距离（简单）
算法原理：
Q1解法：暴力枚举
时间复杂度O(M)（其中 M = 202504）
思路很简单，遍历每个数，取出每一位相加，只要累加和sum能被5整除就cnt++，最后打印一下cnt即可
Q2解法：暴力枚举
时间复杂度O(M)（其中 M = 20250412）
思路很简单，遍历每个数，取出每一位，如果是0、2或5就给对应计数++，然后判断一下是否满足cnt0≥1、cnt2≥2、cnt5≥1，符合就及时cnt++，然后break，最后打印cnt即可
Q3解法：模拟
时间复杂度O (m×n)
思路很简单，就是模拟，进行m次变换，每次变换a[i]=a[i]×Inetger.bitCount(a[i])
易错点：要按格式输出结果
例如：写成如下仅能通过10%测试用例
for(int i=0;i<n;i++) System.out.print(a[i]);但写成如下就可通过100%测试用例
for(int i=0;i<n;i++){ if(i>0) System.out.print(" "); System.out.print(a[i]); }Q4解法：贪心
时间复杂度O(nlogn)
贪心原理：“任何不按顺序配对的方案，都可以通过调整，得到一个总长度更小的方案”
贪心结论：“能连就连”
这里我们避免了复杂的证明，就拿一个典型的例子来形象的理解一下👇
我们可以举个极端一点的例子，下面0代表一单位距离，Xᵢ 代表第 i 台显示器，Yᵢ 代表第 i 台插座
[0,0,X₁,0,0,Y₁,0,0,0,X₂,0,0,0,0,0,0,0,0,0,Y₂]
非贪心情况：X₁→Y₂，X₂→Y₁，此时会导致中间的0,0,0重复计算了两次
贪心情况：X₁→Y₁，X₂→Y₂，此时会导致中间的0,0,0直接被剩下了，节省了6个单位长度，因此最优贪心就是：“能连就连”
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<=202504;i++){ int t=i,sum=0; while(t!=0){ sum+=(t%10); t/=10; } if(sum%5==0) 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); //在此输入您的代码... int cnt=0; for(int i=1;i<=20250412;i++){ int t=i,cnt0=0,cnt2=0,cnt5=0; while(t!=0){ int cur=t%10; if(cur==0) cnt0++; else if(cur==2) cnt2++; else if(cur==5) cnt5++; t/=10; if(cnt0>=1&&cnt2>=2&&cnt5>=1){ cnt++; break; } } } System.out.println(cnt); scan.close(); } }Q3
import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); //在此输入您的代码... int n=scan.nextInt(); int[] a=new int[n]; for(int i=0;i<n;i++) a[i]=scan.nextInt(); int m=scan.nextInt(); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ a[j]=a[j]*Integer.bitCount(a[j]); } } for(int i=0;i<n;i++){ if(i>0) System.out.print(" "); System.out.print(a[i]); } scan.close(); } }Q4
import java.util.Scanner; import java.util.Arrays; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); //在此输入您的代码... int n=scan.nextInt(); int[] a=new int[n]; int[] b=new int[n]; for(int i=0;i<n;i++) a[i]=scan.nextInt(); for(int i=0;i<n;i++) b[i]=scan.nextInt(); long sum=0; //贪心：遇到就连 Arrays.sort(a); Arrays.sort(b); for(int i=0;i<n;i++) sum+=Math.abs(a[i]-b[i]); System.out.println(sum); scan.close(); } }