文章目录
最小的十六进制Excel的列相等日期取数最大连通分块哪一天信号覆盖清理水草最长滑行区间最小值单调队列O(n)优先队列O(NlgN)线段树O(NlgN)
个人Java题解，据我所知题目一样的，可以参考一下，欢迎评论区讨论
最小的十六进制
问题描述
请找到一个大于 2022 的最小数，这个数转换成十六进制之后，所有的数位（不含前导 0）都为字母（A 到 F）。
请将这个数的十进制形式作为答案提交。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
参考题解
直接模拟即可,这里我写的是死循环，找到答案就退出即可
public class Main { public static void main(String[] args) { for (int x = 2022; ; x++) { if (check(x)) { System.out.println(x); return; } } } private static boolean check(int x) { for (char c : Integer.toHexString(x).toCharArray()) { if (!Character.isAlphabetic(c)) return false; } return true; }}答案：2730
Excel的列
问题描述
在 Excel 中，列的名称使用英文字母的组合。前 26 列用一个字母，依次为 A 到 Z，接下来 26*26 列使用两个字母的组合，依次为 AA 到 ZZ。
请问第 2022 列的名称是什么？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。
参考题解
1个字母的列有26个，2个字母的列有2626个，3个字母的列有2626*26 = 17,576个，所以2022列一定是3个字母的组合，我们可以直接枚举3个字母的组合就可以找出答案了
public class Main { public static void main(String[] args) { int k = 676 + 26; for (char i = 'A'; i <= 'Z'; i++) { for (char j = 'A'; j <= 'Z'; j++) { for (char l = 'A'; l <= 'Z'; l++) { if (++k == 2022) { System.out.println(i + "" + j + "" + l); return; } } } } }}答案：BYT
相等日期
问题描述
对于一个日期，我们可以计算出年份的各个数位上的数字之和，也可以分别计算月和日的各位数字之和。请问从 1900 年 1 月 1 日至 9999 年 12 月 31 日，总共有多少天，年份的数位数字之和等于月的数位数字之和加日的数位数字之和。
例如，2022年11月13日满足要求，因为 2+0+2+2=(1+1)+(1+3) 。
请提交满足条件的日期的总数量。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
参考题解
简单模拟，在此强烈建议Java组的同学学习一下LocalDate和LocalDateTime这两个类，处理日期和时间非常方便，蓝桥杯也是很喜欢出日期和时间的题目。
import java.time.LocalDate;public class Main { public static void main(String[] args) { LocalDate start = LocalDate.of(1900, 1, 1); LocalDate end = LocalDate.of(9999, 12, 31); int ans = 0; while (!start.isAfter(end)) { int y = start.getYear(), m = start.getMonthValue(), d = start.getDayOfMonth(); int e = 0; for (; y > 0; y /= 10) e += y % 10; for (; m > 0; m /= 10) e -= m % 10; for (; d > 0; d /= 10) e -= d % 10; if (e == 0) ans++; start = start.plusDays(1); } System.out.println(ans); }}答案：70910
取数
问题描述
小蓝有 30 个数，分别为：99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。
小蓝可以在这些数中取出两个序号不同的数，共有 30*29/2=435 种取法。
请问这 435 种取法中，有多少种取法取出的两个数的乘积大于等于 2022 。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
参考题解
暴力循环，注意题目中的描述，取的两个数是不分顺序的，假设j<i, 如果两层for循环都遍历到30的话会出现a[i]*a[j] 和 a[j]*a[i] 都取了一次，有重复。所以我们设置第二层遍历到i-1即可。
public class Main { public static void main(String[] args) { int[] a = {99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77}; int ans = 0; for (int i = 0; i < a.length; i++) { for (int j = 0; j < i; j++) { if (a[i] * a[j] >= 2022) ans++; } } System.out.println(ans); }}答案：189
最大连通分块
问题描述
小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 或 1 。
110010000011111110101001001001101010111011011011101001111110010000000001010001101100000010010110001111100010101100011110001011101000100011111111111010000010010101010111001000010100101100001101011101101011011001000110111111010000000110110000010101100100010000111000100111100110001110111101010011001011010011011010011110111101111001001001010111110001101000100011101001011000110100001101011000000110110110100100110111101011101111000000101000111001100010110000100110001001000101011001001110111010001011110000001111100001010101001110011010101110001010101000110001011111001010111111100110000011011111101010011111100011001110100101001011110011000101011000100111001011011010001101011110011011111010111110010100101000110111010110001110000111100100101110001011101010001100010111110111011011111100001000001100010110101100111001001111100100110000001101001110010000000111011110000011000010101000111000000110101101100100011101011111001101001010011111110010111101000010000111110010100110101100001101111101010011000110101100000110001010110101101100001110000100010001001010100010110100100001000011100100000100001101010101001101000101101000000101111110001010101101011010101000111110110000110100000010011111111100110010101111000100000100011000010001011111001010010001010110001010001010001110101010000100010011101001010101101101010111100101001111110000101100010111111100000100101010000001011101100001101011110010000010010110000100001010011111100011011000110010011110010100011101100101111101000001011100001011010001110011000101000101000010010010110111000010101111001101100110011100100011100110011111000110011001111100001110110111001001000111111011000110001000110111011001011110010010010110101000011111011110011110110110011011001011010000100100101010110000010011010011110011100101010101111010001001001111101111101110011101如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置，则称两个位置连通。与某一个标为 1 的位置连通的所有位置（包括自己）组成一个连通分块。
请问矩阵中最大的连通分块有多大？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
参考题解
广度优先或者深度优先搜索都可以，这里我写的是深度优先搜索，数组可以复制到控制台输入方便一些。
遍历数组，每遍历到1就进入搜索，联通分块是相互独立的，在搜索的同时把图中的1改成0，这样不会影响答案，也不会重复搜索了，还不用多开标记数组。
import java.util.Scanner;public class Main { public static void main(String[] args) { new Main().run(); } int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1}; char[][] mat; private void run() { Scanner sc = new Scanner(System.in); mat = new char[30][60]; for (int i = 0; i < 30; i++) { mat[i] = sc.nextLine().toCharArray(); } int ans = 0; for (int i = 0; i < 30; i++) { for (int j = 0; j < 60; j++) { if (mat[i][j] == '1') ans = Math.max(ans, dfs(i, j)); } } System.out.println(ans); } private int dfs(int i, int j) { int ans = 1; mat[i][j] = '0'; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x < 0 || y < 0 || x >= 30 || y >= 60 || mat[x][y] == '0') continue; ans += dfs(x, y); } return ans; }}答案：148
哪一天
问题描述
给定一天是一周中的哪天，请问 n 天后是一周中的哪天？
输入格式
输入第一行包含一个整数 w，表示给定的天是一周中的哪天，w 为 1 到 6 分别表示周一到周六，w 为 7 表示周日。
第二行包含一个整数 n。
输出格式
输出一行包含一个整数，表示 n 天后是一周中的哪天，1 到 6 分别表示周一到周六，7 表示周日。
样例输入
6
10
样例输出
2
评测用例规模与约定
对于所有评测用例，1 <= n <= 1000000。
参考题解
签到题，基础不是很好的同学要注意一下边界情况
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int w = sc.nextInt(), n = sc.nextInt(); System.out.println((--w + n) % 7 + 1); }}信号覆盖
问题描述
小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 (0, 0)， 东南角坐标为 (W, 0)， 西北角坐标为 (0, H)， 东北角坐标为 (W, H)。其中 W, H 都是整数。
他在 n 个位置设置了信号塔，每个信号塔可以覆盖以自己为圆心，半径为 R 的圆形（包括边缘）。
为了对信号覆盖的情况进行检查，小蓝打算在区域内的所有横纵坐标为整数的点进行测试，检查信号状态。其中横坐标范围为 0 到 W，纵坐标范围为 0 到 H，总共测试 (W+1) * (H+1) 个点。
给定信号塔的位置，请问这 (W+1)*(H+1) 个点中有多少个点被信号覆盖。
输入格式
输入第一行包含四个整数 W, H, n, R，相邻整数之间使用一个空格分隔。
接下来 n 行，每行包含两个整数 x, y，表示一个信号塔的坐标。信号塔可能重合，表示两个信号发射器装在了同一个位置。
输出格式
输出一行包含一个整数，表示答案。
样例输入
10 10 2 5
0 0
7 0
样例输出
57
评测用例规模与约定
对于所有评测用例，1 <= W, H <= 100，1 <= n <= 100, 1 <= R <= 100, 0 <= x <= W, 0 <= y <= H。
参考题解
编程题首先看测试用例数据范围，暴力做法是遍历每个点，检查点是否在，任何一个信号塔的范围内，遍历点的时间复杂度是O(WH),检查信号塔的时间复杂度是O(n)，计算该点到信号塔的圆心处的距离是否小于等于半径的长度，一般是跟R的平方直接对比，因为Math.sqrt()函数开方的话可能会有精度损失，能用整型用整型。
算法时间复杂度是O(WHn) 最坏情况下是O(1e6)。不会超时，可以暴力。时间复杂度在O(10^7)的量级内一般不会超时.
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int W = sc.nextInt(), H = sc.nextInt(), n = sc.nextInt(), R = sc.nextInt(); int[][] a = new int[n][2]; for (int i = 0; i < n; i++) { a[i][0] = sc.nextInt(); a[i][1] = sc.nextInt(); } int ans = 0; for (int i = 0; i <= W; i++) { for (int j = 0; j <= H; j++) { if (check(i, j, a, R)) ans++; } } System.out.println(ans); } private static boolean check(int i, int j, int[][] a, int r) { for (int[] b : a) { int dx = i - b[0], dy = j - b[1]; if (dx * dx + dy * dy <= r * r) return true; } return false; }}清理水草
问题描述
小蓝有一个 n * m 大小的矩形水域，小蓝将这个水域划分为 n 行 m 列，行数从 1 到 n 标号，列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。
现在，这个水域长满了水草，小蓝要清理水草。
每次，小蓝可以清理一块矩形的区域，从第 r1 行（含）到第 r2 行（含）的第 c1 列（含）到 c2 列（含）。
经过一段时间清理后，请问还有多少地方没有被清理过。
输入格式
输入第一行包含两个整数 n, m，用一个空格分隔。
第二行包含一个整数 t ，表示清理的次数。
接下来 t 行，每行四个整数 r1, c1, r2, c2，相邻整数之间用一个空格分隔，表示一次清理。请注意输入的顺序。
输出格式
输出一行包含一个整数，表示没有被清理过的面积。
样例输入1
2 3
2
1 1 1 3
1 2 2 2
样例输出1
2
样例输入2
30 20
2
5 5 10 15
6 7 15 9
样例输出2
519
评测用例规模与约定
对于所有评测用例，1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。
参考题解
直接暴力遍历，千言万语尽在代码中
算法时间复杂度是O(nmt) 最坏情况下是O(1e6)。不会超时，可以暴力。时间复杂度在O(10^7)的量级内一般不会超时
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); boolean[][] mat = new boolean[n + 1][m + 1]; int t = sc.nextInt(); while (t-- > 0) { int r1 = sc.nextInt(), c1 = sc.nextInt(); int r2 = sc.nextInt(), c2 = sc.nextInt(); for (int i = r1; i <= r2; i++) { for (int j = c1; j <= c2; j++) { mat[i][j] = true; } } } int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!mat[i][j]) ans++; } } System.out.println(ans); }}最长滑行
问题描述
小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 n 行 m 列的矩阵来表示场地，矩阵中的数值表示场地的高度。
如果小蓝在某个位置，而他上、下、左、右中有一个位置的高度（严格）低于当前的高度，小蓝就可以滑过去，滑动距离为 1 。
如果小蓝在某个位置，而他上、下、左、右中所有位置的高度都大于等于当前的高度，小蓝的滑行就结束了。
小蓝不能滑出矩阵所表示的场地。
小蓝可以任意选择一个位置开始滑行，请问小蓝最多能滑行多远距离。
输入格式
输入第一行包含两个整数 n, m，用一个空格分隔。
接下来 n 行，每行包含 m 个整数，相邻整数之间用一个空格分隔，依次表示每个位置的高度。
输出格式
输出一行包含一个整数，表示答案。
样例输入
4 5
1 4 6 3 1
11 8 7 3 1
9 4 5 2 1
1 3 2 2 1
样例输出
7
样例说明
滑行的位置一次为 (2, 1), (2, 2), (2, 3), (3, 3), (3, 2), (4, 2), (4, 3)。
评测用例规模与约定
对于 30% 评测用例，1 <= n <= 20，1 <= m <= 20，0 <= 高度 <= 100。
对于所有评测用例，1 <= n <= 100，1 <= m <= 100，0 <= 高度 <= 10000。
参考题解
这题与前面的选择题最大连通分块类似，大的点可以移动到小的点，暴力解法是遍历每一个点开始dfs暴搜，每一遍的dfs最坏情况下时间复杂度是O(nm)，暴力算法总时间复杂度是O(n 2 ^2 2m 2 ^2 2).最坏情况下O(1e8)会超时。
所以我们要考虑优化，在一次遍历中访问到一个点 p的时候，一定是从高度更高的点转移过来的，然后前一个点也是从更高的点转移过来的，当前点为p的情况下，高度低于点P的点一定都没访问过。
也就是说，对于每一个点，从它开始的dfs能遍历的点是一样的，dfs结果也是一样。所以我们可以用一个二维数组维护每一个dfs(i, j)的dfs的结果，在下一次遇到dfs(i, j)时可以直接返回结果，减少重复遍历。这就是记忆化深度遍历.难理解的同学多看代码
本题中用记忆化深度遍历时间复杂度能降为O(nm),每个点只会访问常数次。
import java.io.*;public class Main { public static void main(String[] args) { new Main().run(); } int[][] mat, dp; int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1}; int n, m; private void run() { n = nextInt(); m = nextInt(); mat = new int[n][m]; dp = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { mat[i][j] = nextInt(); } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ans = Math.max(ans, dfs(i, j)); } } out.println(ans); out.close(); } private int dfs(int i, int j) { if (dp[i][j] > 0) return dp[i][j]; int ans = 1; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x < 0 || y < 0 || x >= n || y >= m || mat[i][j] <= mat[x][y]) continue; ans = Math.max(ans, dfs(x, y) + 1); } dp[i][j] = ans; return ans; } StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(System.out); int nextInt() { try { in.nextToken(); } catch (IOException e) { throw new RuntimeException(e); } return (int) in.nval; }}区间最小值
小蓝有一个序列a[1], a[2]. … a[n].
给定一个正整数k，请问对于每一个1到n之间的序号i，a[i-k], a[i-k+1]… a[i+k]这2k+1个数中的最小值是多少?当某个下标超过1到n的范围时，数不存在，求最小值时只取存在的那些值。
输入格式
输入的第一行包含一整数n。
第二行包含n个整数，分别表示a[1], a[2]. … a[n]。第三行包含一个整数k。
输出格式
输出一行，包含n个整数，分别表示对于每个序号求得的最小值。
样例输入
5
5 2 7 4 3
1
样例输出
2 2 2 3 3
评测用例规模与约定
对于30%的评测用例，1<= n<= 1000，1 <= a[i]<=1000。
对于50%的评测用例，1<= n<= 10000，1 <= a[]<=10000。
对于所有评测用例，1<= n<= 1000000，1 <= a[i]<=100000。
单调队列O(n)
题目可以看成一个长度为2k+1的滑动窗口求最小值，题目的n最大是1000000，所以我们要O(1)或者O(lgn)时间复杂度内求出一个区间内的最小值。我们需要求出的是滑动窗口的最小值，如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i<j），并且 i对应的元素不小于 j 对应的元素（a[i]a[j]），那么会发生什么呢？当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。因此，由于 a[j]的存在，a[i] 一定不会是滑动窗口中的最大值了，也就是说，a[j]是比a[i]更优的一个值，所以我们可以将 a[i] 永久地移除。当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。同时我们需要在窗口移动时删除左边界所以我们可以维护一个下标递增数组值也递增的单调队列 每个元素只会访问2次，时间复杂度为O(n), 不懂的同学收藏多看代码理解
import java.io.*;import java.util.Deque;import java.util.LinkedList;public class Main { public static void main(String[] args) { new Main().run(); } public void run() { int n = nextInt(); int[] a = new int[n + 1]; for (int i = 1; i <= n; i++) a[i] = nextInt(); int k = nextInt(); Deque<Integer> d = new LinkedList<>(); for (int i = 1; i <= k; i++) { while (!d.isEmpty() && a[i] <= a[d.peekLast()]) d.removeLast(); d.addLast(i); } for (int i = 1; i <= n; i++) { int l = i - k, r = i + k; if (r <= n) { while (!d.isEmpty() && a[r] <= a[d.peekLast()]) d.removeLast(); d.addLast(r); } while (!d.isEmpty() && d.peekFirst() < l) d.removeFirst(); out.print(a[d.peekFirst()] + " "); } out.close(); } StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(System.out); int nextInt() { try { in.nextToken(); } catch (IOException e) { throw new RuntimeException(e); } return (int) in.nval; }}优先队列O(NlgN)
对于「最大值」和「最小值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的小根堆可以帮助我们实时维护一系列元素中的最小值。
对于本题而言，初始时，我们将数组 a 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，同时把不满足左边界条件的值删除，此时堆顶的元素就是堆中所有元素的最小值。
Java有提供PriorityQueue类实现优先队列，插入，查找，删除的时间复杂度都是O(lgN)。C++的STL有作用一样的priority_queue，python也有，同学们可以去学习一下使用方法和如何自定义比较器实现大顶堆
优先队列比单调队列好理解很多，算法总时间复杂度是O(NlgN)
import java.io.*;import java.util.PriorityQueue;public class Main { public static void main(String[] args) { new Main().run(); } public void run() { int n = nextInt(); int[] a = new int[n + 1]; for (int i = 1; i <= n; i++) a[i] = nextInt(); int k = nextInt(); PriorityQueue<Integer> q = new PriorityQueue<>(); for (int i = 1; i <= k; i++) q.add(a[i]); for (int i = 1; i <= n; i++) { int l = Math.max(0, i - k), r = Math.min(n + 1, i + k); if (l >= 2) q.remove(a[l - 1]); if (r <= n) q.add(a[r]); out.print(q.peek()+" "); } out.close(); } StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(System.out); int nextInt() { try { in.nextToken(); } catch (IOException e) { throw new RuntimeException(e); } return (int) in.nval; }}线段树O(NlgN)
这个就不讲了，代码比较多，直接上代码，还有一种解法是ST表，交给评论区的各位了
import java.io.*;public class Main { public static void main(String[] args) { new Main().run(); } class ST { int l, r, min; } ST[] t; int[] a; public void run() { int n = nextInt(); a = new int[n + 1]; for (int i = 1; i <= n; i++) a[i] = nextInt(); int k = nextInt(); t = new ST[n * 4]; for (int i = 0; i < t.length; i++) t[i] = new ST(); build(1, 1, n); for (int i = 1; i <= n; i++) { int l = Math.max(1, i - k), r = Math.min(n, i + k); out.print(ask(1, l, r) + " "); } out.close(); } private int ask(int p, int l, int r) { if (l <= t[p].l && t[p].r <= r) return t[p].min; int mid = (t[p].l + t[p].r) / 2; int ans = Integer.MAX_VALUE; if (l <= mid) ans = Math.min(ans, ask(p * 2, l, r)); if (r > mid) ans = Math.min(ans, ask(p * 2 + 1, l, r)); return ans; } private void build(int p, int l, int r) { t[p].l = l; t[p].r = r; if (l == r) { t[p].min = a[l]; return; } int mid = (l + r) / 2; build(p * 2, l, mid); build(p * 2 + 1, mid + 1, r); t[p].min = Math.min(t[p * 2].min, t[p * 2 + 1].min); } StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(System.out); int nextInt() { try { in.nextToken(); } catch (IOException e) { throw new RuntimeException(e); } return (int) in.nval; }}以上就是蓝桥杯第十四届第三期模拟赛所有的题目了，希望本篇文章的讲解对你有所帮助，感谢阅读，觉得写得还行的可以可以点个赞ovo~