[数据结构与算法]2022年第十三届蓝桥杯省赛Java B组（部分）

2022年第十三届蓝桥杯省赛Java B组

第一题：星期计算

暴力计算即可

public class Main {

	public static void main(String[] args) {
//		long s = 1L;
//		for(int i = 1; i <= 22;i++) {
//			s = s * 20 % 7;
//		}
//		System.out.println(s);
		System.out.println("7");
	}
}

第二题：山

这道题写出回文和满足左半单调不减即可（因为如果是回文，那如果左边单调不减，右边肯定单调不增），只是可能要稍微考虑长度为奇或偶的中间取值

public class Main {

	public static void main(String[] args) {
//		boolean flag = false;
//		long res = 0;
//		for(int i = 2022; i <= 2022222022;i++) {
//			String t = i + "";
//			flag = false;
//			for(int j = 0,k = t.length() - 1;j < (t.length() + 1) / 2 ;j++,k--) {
//				if(t.charAt(j) != t.charAt(k)) {
//					flag = true;
//					break;
//				}else {
//					if(j!= 0 && t.charAt(j) < t.charAt(j - 1)){
//						flag = true;
//						break;
//					}
//				}
//			}
//			if(!flag) {
//				res++;
//			}
//		}
//		System.out.println(res);
		System.out.println(3138);
	}

}

第三题：字统计

遍历的时候把相同字母的次数加上，然后在此过程中更新最大值即可。

public class Main {
    //数组0~25分别表示A~Z
	static int[] a = new int[26];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
        //字母出现最多次的次数
		int max = -1;
		for(int i = 0; i < s.length();i++) {
			char ch = s.charAt(i);
			a[ch - 'A']++;
            //保存在此过程中字母出现次数的最大值
			max = Math.max(a[ch - 'A'],max);;
		}
		String t = "";
//		System.out.println(max);
		for(int i = 0; i < a.length;i++) {
//			System.out.print(a[i] + " ");
            //如果当前字母跟最大值相等，保存起来，再输出（也可以直接输出）
			if(a[i] == max) {
				t+=(char)(i + 'A');
			}
		}
		System.out.println(t);
	}
}

第四题：最少刷题数

这道题是一道看起来不难但是陷阱重重的题，我们首先看下数据规模，对于100%的数据，N是十万级别，所以我们的时间复杂度不能超过O(nlogn)，如果为O($n^2$)则会超时。

然后这题没有说数字不能重复，所以我们还要考虑数字重复问题，还要考虑中间值问题，因为为我们的要求是每个学生只要还要再刷多少道题，所以我们肯定是要求出排完序后中间值，对于中间值就要考虑奇偶，上取整还是下取整。我这里是上取整为例

这里思路主要参考2022 十三届蓝桥杯 JavaB组省赛 个人题解这位大佬的。

整理后，我的思路是，先创一个数组b，然后对数组b排序。然后求出中间值u的个数、比中间值大的个数ur、比中间值小的个数ul，然后开始遍历数组a，下标从0开始，即0~(n-1)，然后每次根据数组a找出对应的在数组b中的位置pos。

然后开始判断b[pos]与u之间的关系

• b[pos] > u
  • 不需要任何条件就能满足
• b[pos] == u
  • 如果ur <= ul的话，则你不刷题也能满足条件，即目标题数为u题,就不用加了，直接输出0
  • 反之，则说明这些人需要再刷1题，即目标题数为u + 1题，就需要输出1
• b[pos] < u
  • 我们先将b[pos]加到u，我们会知道此时ul就会减1，而ur不变（因为b[pos]此时跟u相等了），所以如果此时ur <= ul - 1 ,满足条件，就只需要加到u即可，即结果为u - a[i]
  • 反之，这些人的题数必须定为u + 1题

接下来就是代码实现了

public class Main {
	static int N = 100010;
	static int[] a = new int[N];
	static int[] b = new int[N];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i = 0; i < n;i++) {
			a[i] = sc.nextInt();
			b[i] = a[i];
		}
		Arrays.sort(b,0,n);
//		求出中间值
		int u = b[n / 2];
		boolean flag = false;
//		求出比u大的个数和比u小的个数
		int ul = 0,ur = 0;
//		求出u的个数
		int cntu = 0;
		for(int i = 0; i < n;i++) {
			if(b[i] == u) {
				cntu++;
				if(!flag) {
					ul = i;
					flag = true;
				}
			}
		}
		ur = n - cntu - ul;
//		System.out.println(ul + " " + ur);
//		for(int i = 0; i < n;i++) System.out.print(b[i] + " ");
//		判断与u相同的数
		for(int i = 0; i < n;i++) {
//			System.out.println(a[i]);
			int pos = Arrays.binarySearch(b,0,n, a[i]);
//			System.out.println(pos + " ");
//			如果找的值不是中间值
			if(b[pos] < u) {
				//如果右边小于左边减1
				if(ur <= ul - 1) {
					System.out.print(u - a[i] + " ");
				}else {
					System.out.print(u + 1 - a[i] + " ");
				}
			}else if(b[pos] > u) {
				System.out.print(0 + " ");
			}else {
				if(ur <= ul) System.out.print(0 + " ");
				else System.out.print(1 + " ");
			}
		}
	}
}

第五题：求阶乘

参考博客：2022年第十三届蓝桥杯B组 试题 E: 求阶乘

这道题主要是要知道满足位数为0，只能是2乘上5的形式，而2的个数远比5多，所以我们考虑5的个数就可以。

我们还要注意有些数是能分两个5的，比如25 = 5 * 5，能分出两个，所以能多出一个0.（我没注意，直接结束。

我们首先看数据，对于100%的数据，K的取值范围为[1,$10^{18}$]，一般来说就用到long了，我们先算出Integer的最大值的阶乘有多少个零，如果不够就要考虑使用long的最大值的阶乘有多少个零。

 // 求x的阶乘后边有多少个0    
public static long calc(long x){
    long res = 0;
    while (x!=0){
        res = res+x/5;
        x/=5;
    }
    return res;
}
public static void main(String[] args){
    System.out.println("Integer: " + calc(Integer.MAX_VALUE/2));
    System.out.println("Long: " + calc(Long.MAX_VALUE/2 ));
}

对于输出结果，注意我们这里要使用包装类，因为基础类型没有MAX_VALUE属性。

从结果我们可以看出，要使用Long类型。

由于0的个数是在随着数的增加，单调不减的，所以我们可以使用二分查找来降低复杂度，实现O(logn)，否则遍历的话O(n)肯定会超时。

import java.util.Scanner;
public class Main {
	public static long calc(long x) {
		long res = 0;
		while(x != 0) {
			res = res + x / 5;
			x/=5;
		}
		return res;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Long k = sc.nextLong();
		long l = 0,r = Long.MAX_VALUE - 5;//防止溢出
		while(l < r) {
			long mid = (l + r) / 2;
			if(k <= calc(mid)) {
				r = mid;
			}else {
				l = mid + 1;
			}
		}
		if(calc(r) != k) {
			System.out.println(-1);
		}else {
			System.out.println(r);
		}
		
	}
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖