2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

第十三届蓝桥杯省赛JavaB组真题（Java题解解析）_13届蓝桥杯java组

作者：2023面试高手 | 2024-04-22 01:51:51

踩

13届蓝桥杯java组

前言

总共150分

初次解题过程：

A：+0分（答案算错了(计算得6，最终答案为7)，想到是采用步骤做取余计算，但是没有使用多个样例来进行测试，就直接取答案了。）
B：+0分（答案算错了(计算得644，最终答案为3138)），我裂开，题意看错了，前一半是进行升序(实际上可以<=，我看成是只能<)，实际上我们只需要对每一个字符判断前面一半是升序 && 是回文即可解决。(60秒)
C：+10分
D：+1（10个案例点就过了1个）
E：+0（本来认为是找规律题，没想到考的是算数基本定理）
F：+1.5（写了个暴力，优化需要使用优先队列 使用空间换时间）
G：+10（写了递归搜索就过了5个用例，优化使用DP）
I：
J：
1
2
3
4
5
6
7
8
9

第十三届蓝桥杯省赛JavaB组真题

试题A：星期计算（5分）

题目

题解

答案：7

解法1：步骤取余计算（int即可）

public class Main {
	public static void main(String[] args) {
		int temp = 20;
		// 循环22次
		for (int i = 1; i <= 21; i++) {
			temp = (temp * 20) % 7;
		}
		// 打印最终结果
		// 其中(5 + temp) % 7是计算得到目标星期x的x下标(从0开始的)，所以最后要进行+1。
		System.out.println((5 + temp) % 7 + 1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

解法2：使用API

①直接使用Math.pow

public class Main {
	public static void main(String[] args) {
		System.out.println(Math.pow(20, 22) % 7 + 6);
	}
}
1
2
3
4
5

②使用BigInteger

import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		BigInteger bg = new BigInteger("20");
		//pow取次方数，remainder进行取余
		bg = bg.pow(22).remainder(BigInteger.valueOf(7)).add(BigInteger.valueOf(6));
		System.out.println(bg);
	}
}
1
2
3
4
5
6
7
8
9
10

试题B：山（5分）

题目

题解

本题由于是填空题，可以直接写暴力来计算答案。

暴力法：枚举[2022, 2022222022]，进行check山型递增递减情况以及回文。

解法1：暴力

非调用API版本：

public class Main {

	public static boolean huiwen(int num) {
		char[] chs = String.valueOf(num).toCharArray();
		for (int l = 0, r = chs.length - 1; l <= r; l++, r--) {
			if (chs[l] != chs[r])
				return false;
		}
		return true;
	}

	public static boolean islianxu(int num) {
		char[] chs = String.valueOf(num).toCharArray();
		int n = chs.length;
		int b1 = n % 2 == 1 ? n / 2 : n / 2 - 1;
		int b2 = n / 2;
		// [0, b1] 单调增
		for (int i = 1; i <= b1; i++) {
			if (chs[i] <= chs[i - 1])
				return false;
		}
		// [b2, n - 1]单调减
		for (int i = b2 + 1; i < n; i++) {
			if (chs[i] >= chs[i - 1])
				return false;
		}
		return true;
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		int ans = 0;
		for (int i = 2022; i <= 2022222022; i++) {
			if (islianxu(i) && huiwen(i)) {
				ans++;
			}
		}
		System.out.println(ans);
		long end = System.currentTimeMillis();
		System.out.println("" + ((double) (end - start) / 1000) + "秒");
	}
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

调用API版本：

public class Main {

	// 只需要比较前半部分
	public static boolean islianxu(int num) {
		char[] arr = String.valueOf(num).toCharArray();
		int n = arr.length;
		int len = n % 2 == 0 ? n / 2 - 1 : n / 2;
		// 比较前半部分
		for (int i = 1; i <= len; i++) {
			if (arr[i] < arr[i - 1])
				return false;
		}
		return true;
	}

	// 反转字符串来进行比较（判断是否是回文）
	public static boolean huiwen(int num) {
		String targetStr = (new StringBuilder(num + "")).reverse().toString();
		return String.valueOf(num).equals(targetStr);
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		int ans = 0;
		for (int i = 2022; i <= 2022222022; i++) {
			if (islianxu(i) && huiwen(i)) {
				ans++;
			}
		}
		System.out.println(ans);
		long end = System.currentTimeMillis();
		System.out.println("" + ((double) (end - start) / 1000) + "秒");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

试题C：字符统计（10分）

题目

蓝桥杯官网题-字符统计

题解（哈希）

哈希走一遍。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws Exception {
		int[] cnts = new int[26];
		String str = cin.readLine();
		char[] chs = str.toCharArray();
		int max = 0;
		for (char ch : chs) {
			cnts[ch - 'A']++;
			max = Math.max(cnts[ch - 'A'], max);
		}
		for (int i = 0; i < 26; i++) {
			if (cnts[i] == max) {
				System.out.printf("%c", (char) (i + 'A'));
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

本地调试：

蓝桥杯官网提交：

试题D：最少刷题数（10分）

题目

蓝桥杯官网题-最少刷题数

题解

题目要求：刷题比他多的学生人数不超过刷题比他少的人数。多的 <= 少的。

解法1：暴力（排序），时间复杂度都是在排序上，确定n个小朋友多做的时间复杂度是O(n)。

思路：
1、对所有小朋友做的题数进行排序
2、确定一个中间值target，分别使用两个计数变量(l、r)记录>target与<target的个数。
3、若是l == r，那么我们直接将<target的值增加到target即可；若是l<r，那么此时我们需要将目标值放到target+1上，此时r<=l（必然情况）
4、枚举每一个小朋友的解题数与target作比较，若是>=target那么即可直接输出0，若是<target则需要进行分情况讨论：讨论关于l == r ? 1 : 0
		情况1：12778  target = 7, l = 2 r = 1， 此时a[i] = 2时，我们只需要7-2即可
        情况2: 77788  target = 8(由于l < r，增加1), l = 0, r = 2, 此时a[i] = 7，为8-7即可
        情况3: 11788，target = 7，l = 2, r = 2，此时a[i] = 1，我们需要将a[i]提升到target+1，才能保证r<=l
1
2
3
4
5
6
7
8

解法1：排序（过7个点）

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.util.*;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static final int N = 100010;
    static int[] a = new int [N];
    static int n;

    public static void main(String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine());
        String[] ss = cin.readLine().split(" ");
        for (int i = 0; i < n; i ++) {
          a[i] = Integer.parseInt(ss[i]);
        }
        //克隆，来进行排序
        int[] temp = a.clone();
        Arrays.sort(temp, 0, n);
        //target：目标值，l：比target小的数量，r：比target大的数量
        int target = temp[n / 2], l = 0, r = 0;
        for (int i = 0; i < n; i ++) {
          if (temp[i] > target) {
              r ++;
          }else if (temp[i] < target) {
              l ++;
          }
        }
        //由于我们本身就是取的排序中间值，若是大于中间值的数量  >  小于中间值的数量
        //那么我们的目标值就需要进行+1
        if (l < r) target ++;
        //接着来进行输出结果
        for (int i = 0; i < n; i ++) {
          if (a[i] >= target) {
            out.printf("%d ", 0);
          }else {
            //考虑到将当前值提升到target 还是 target+1（取决于左右两边>与<数的情况）
            //当前的值为a[i] < target，讨论关于
            //情况1：12778  target = 7, l = 2 r = 1， 此时a[i] = 2时，我们只需要7-2即可
            //情况2: 77788  target = 8(由于l < r，增加1), l = 0, r = 2, 此时a[i] = 7，为8-7即可
            //情况3: 11788，target = 7，l = 2, r = 2，此时a[i] = 1，我们需要将a[i]提升到target+1，才能保证r<=l
            out.printf("%d ", target - a[i] + (l == r ? 1 : 0));
          }
        }
        out.flush();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

试题E：求阶乘（15分）

题目

题解

根据算数基本定理可以将一个数分解成若干个数的乘积。

n! = N = P1a1 P2a2 P3a3 * … Pnan，本题中需要统计的是后缀连续0的个数，那么也就是目标n!中对于10的阶乘个数，又10 = 2 * 5，想要求得目标10，那么我们就需要去匹配多对2与5，此时即为找到min(质因子2的个数，质因子5的个数)，又质因子2的个数是大于5的个数，所以我们可以直接去求质因子为5的个数 == k。

对于一个数n，求得该n!中质因子为5的个数，我们只需要去对n进行不断相除即可求得。

//计算n中有多少个5
public static long check(int num) {
    long res = 0L;
    while (num > 0) {
        res += num / 5;
        num /= 5;
    }
    return res;
}
1
2
3
4
5
6
7
8
9

解法1：枚举1-10⁸，每一个数表示阶乘，来去求得该阶乘的值是否是>=k，找到第一个也就是最小的n即为答案。

这里枚举到10⁸目的就是由于时间复杂度为O(n.logn)，而运算次数为1亿次差不多就是1秒，所以这里取相对在临界位置的值即可。

解法2：由于去check 1-10⁸得到的结果是递增的，那么这个枚举的过程可以修改为二分来进行搜索，此时复杂度可以直接优化为O(logn.logn)，直接ac。

解法1：算数基本定理+枚举（过5个点）

复杂度分析：时间复杂度O(n.logn)；空间复杂度

import java.util.*;
import java.io.*;

public class Main {

    static final Scanner cin = new Scanner(System.in);
    static long N = (long)1e8;
    static long k;

    //计算n中有多少个5
    public static long check(int num) {
        long res = 0L;
        while (num > 0) {
            res += num / 5;
            num /= 5;
        }
        return res;
    }

    public static void main(String[] args) {
        k = cin.nextLong();
        for (int i = 1; i <= N; i ++) {
            //找到第一个>=k情况
            long res = check(i);
            if (res >= k) {
                if (res == k) System.out.println(i);
                else System.out.println(-1);
                return;
            }
        }
        System.out.println(-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

解法2：二分+算数基本定理

复杂度分析：时间复杂度O(logn*logn)；空间复杂度O(1)

import java.util.*;
import java.io.*;

public class Main {

    static final Scanner cin = new Scanner(System.in);
    static long k;

    //计算n中有多少个5
    public static long check(long num) {
        long res = 0L;
        while (num > 0) {
            res += num / 5;
            num /= 5;
        }
        return res;
    }

    public static void main(String[] args) {
        k = cin.nextLong();
        //二分
        long l = 0, r = (long)9e18;
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid) >= k) r = mid;
            else l = mid + 1;
        }
        if (check(r) == k) {
            System.out.println(r);
        }else {
            System.out.println("-1");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

试题F：最大子矩阵（15分）

题目

题解

解法1：暴力（过10%数据）

最大数据量矩阵块数为10万

暴力法

复杂度分析：时间复杂度O(n⁶)；空间复杂度O(n*m)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
	static final int N = 90, M = 100010;
	static int[][] a = new int[N][M];
	static int n, m, limit;

	public static void main(String[] args) throws Exception {
		String[] ss = cin.readLine().split(" ");
		n = Integer.parseInt(ss[0]);
		m = Integer.parseInt(ss[1]);
		for (int i = 1; i <= n; i++) {
			ss = cin.readLine().split(" ");
			for (int j = 1; j <= m; j++) {
				a[i][j] = Integer.parseInt(ss[j - 1]);
			}
		}
		limit = Integer.parseInt(cin.readLine());
		int ans = 0;
		// 暴力
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				// 枚举目标点
				for (int x = i; x <= n; x++) {
					for (int y = j; y <= m; y++) {
						// 遍历区间 起始(i, j) - (x, y)
						int max = 0, min = 0, s = 0;
						for (int xx = i; xx <= x; xx++) {
							for (int yy = j; yy <= y; yy++) {
								s++;// 数量
								max = Math.max(max, a[xx][yy]);
								min = Math.min(min, a[xx][yy]);
							}
						}
						if (max - min <= limit) {
							ans = Math.max(ans, s);
						}
					}
				}
			}
		}
		System.out.println(ans);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

测试：

解法2：单调队列（学习中）

官方题解-学习

中间进行剪枝，中间的使用空间换时间

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
	static final int N = 90, M = 100010;
	static int[][] a = new int[N][M];
	// 前缀和(最大值，最小值)
	static int[][] max = new int[N][M], min = new int[N][M];
	static int n, m, limit;

	public static void main(String[] args) throws Exception {
		String[] ss = cin.readLine().split(" ");
		n = Integer.parseInt(ss[0]);
		m = Integer.parseInt(ss[1]);
		for (int i = 1; i <= n; i++) {
			ss = cin.readLine().split(" ");
			for (int j = 1; j <= m; j++) {
				a[i][j] = Integer.parseInt(ss[j - 1]);
				int preMax = Math.max(Math.max(max[i - 1][j], max[i][j]), max[i - 1][j - 1]);
				max[i][j] = Math.max(preMax, a[i][j]);
				int preMin = Math.max(Math.max(min[i - 1][j], min[i][j]), min[i - 1][j - 1]);
				min[i][j] = Math.max(preMin, min[i][j]);
			}
		}
		limit = Integer.parseInt(cin.readLine());
		// 遍历整个矩阵
		int ans = 0;
		// 枚举所有行
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				// 左右指针
				for (int l = 1, r = 1, s = 0, mmax = 0, mmin = 0; r <= m; r++) {
					// 个数增加
					s += j - i + 1;
					// 矩阵范围最大值确定
					
				}
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

试题G：数组切分（20分）

题目

题解

解法1：暴力枚举（过5个点）

暴力解法：含路径打印

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
	static final int N = 10010;
	static int[] a = new int[N];
	static int n;
	static int ans;

	public static void dfs(int start, int step, List<Integer> res) {
		// 若是start + step > n，越界无法判断，直接结束
		if (start + step > n)
			return;
		// 判断[start, start + step)区间是否是连续
		int max = a[start], min = a[start];
		for (int i = start; i < start + step; i++) {
			max = Math.max(a[i], max);
			min = Math.min(a[i], min);
		}
		// 若是当前无法构成连续区间直接结束
		if (step != 1 && (max - min + 1) != step) {
			return;
		}
		// 表示区间连续
		// 若是此时start+step == n，此时表示构成连续区间
		if (start + step == n) {
			ans++;
			System.out.println(res);
			return;
		}
		// 递归处理，不同的情况
		for (int sstep = 1; sstep <= n; sstep++) {
			res.add(sstep);
			dfs(start + step, sstep, res);
			res.remove(res.size() - 1);
		}
	}

	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(cin.readLine());
		String[] ss = cin.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(ss[i]);
		}
		// 起始步骤枚举
		for (int step = 1; step <= n; step++) {
			ArrayList<Integer> res = new ArrayList<>();
			res.add(step);
			dfs(0, step, res);
		}
		System.out.println(ans);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

暴力解法：不含路径打印

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
	static final int N = 10010;
	static int[] a = new int[N];
	static int n;
	static int ans;

	public static void dfs(int start, int step) {
		// 若是start + step > n，越界无法判断，直接结束
		if (start + step > n)
			return;
		// 判断[start, start + step)区间是否是连续
		int max = a[start], min = a[start];
		for (int i = start; i < start + step; i++) {
			max = Math.max(a[i], max);
			min = Math.min(a[i], min);
		}
		// 若是当前无法构成连续区间直接结束
		if (step != 1 && (max - min + 1) != step) {
			return;
		}
		// 表示区间连续
		// 若是此时start+step == n，此时表示构成连续区间
		if (start + step == n) {
			ans++;
			return;
		}
		// 递归处理，不同的情况
		for (int sstep = 1; sstep <= n; sstep++) {
			dfs(start + step, sstep);
		}
	}

	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(cin.readLine());
		String[] ss = cin.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(ss[i]);
		}
		// 起始步骤枚举
		for (int step = 1; step <= n; step++) {
			ArrayList<Integer> res = new ArrayList<>();
			res.add(step);
			dfs(0, step);
		}
		System.out.println(ans);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

解法2：DP

数组切分（蓝桥杯题解）

import java.util.*;
import java.io.*;

public class Main {

    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 10010, MOD = (int)(1e9 + 7);
    static int[] w = new int[N];
    //表示以第i个为结尾，可以组成多段连续自然数的个数
    static int[] f = new int[N];
    static int n;

    public static void main(String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine());
        String[] ss = cin.readLine().split(" ");
        for (int i = 1; i <= n; i ++) {
            w[i] = Integer.parseInt(ss[i - 1]);
        }
        //初始化
        f[0] = 0;
        for (int i = 1; i <= n; i ++) {
          //设置最大值，最小值
          int max = 0, min = Integer.MAX_VALUE;
          //不断的进行缩减范围 [j, j-1]、[j, j-2]、[j, j-3]作为最后一段区间
          //筛选[j, j-1]、[j, j-2]、[j, j-3]区间符合条件的情况，接着去叠加之前f[j - 1]已经计算好的数量
          for (int j = i; j > 0; j --) {
            max = Math.max(w[j], max);
            min = Math.min(w[j], min);
            if (max - min == i - j) f[i] = (f[i] + f[j - 1]) % MOD;
          }
        }
        System.out.println(f[n]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

试题H：回忆迷宫（20分）

上下左右：udrl

uuuullllddddrrrru

#试题I：红绿灯（25分）

确定思路：贪心

题目

蓝桥杯官方题解-红绿灯

题解

全局最优解一定是和局部最优解有关的。

试题J：拉箱子（25分）

猜想：枚举+DP

题目

题解

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/466229