第十四届蓝桥杯模拟赛（第三期）Java组个人题解
2023年4月3日19:22:18 更新内容：第九题记忆化搜索（dfs+dp），第十题滑动窗口题解。
2023年4月6日09:13:06 更新内容：第八题 "二维差分"降低时间复杂度至O(n²)。
仰望天空，妳我亦是行人.✨
个人主页——); w = Integer.parseInt(split[0]); h = Integer.parseInt(split[1]); n = Integer.parseInt(split[2]); r = Integer.parseInt(split[3]); vis = new boolean[h + 1][w + 1]; for (int i = 0; i < n; i++) { String[] temp = br.readLine().split(” “); bfs(new Node(Integer.parseInt(temp[0]), Integer.parseInt(temp[1]))); } System.out.println(count); } private static void bfs(Node node) { Deque<Node> deque = new ArrayDeque<>(); deque.addLast(node); while (!deque.isEmpty()) { Node poll = deque.pollFirst(); for (int i = 0; i < 4; i++) { int dx = poll.x + dis[i][0]; int dy = poll.y + dis[i][1]; if (dx >= 0 && dx <= w && dy >= 0 && dy <= h && dis(node.x, node.y, dx, dy) <= r && !vis[dx][dy]) { vis[dx][dy] = true; deque.addLast(new Node(dx, dy)); count++; } } } } static double dis(int x1, int y1, int x2, int y2) { int dis = (x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2); return Math.sqrt(dis); } static class Node { int x; int y; public Node(int x, int y) { this.x = x; this.y = y; } }}第八题【未被清理的区域】
问题描述
小蓝有一个 n * m 大小的矩形水域，小蓝将这个水域划分为 n 行 m 列，行数从 1 到 n 标号，列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。
现在，这个水域长满了水草，小蓝要清理水草。
每次，小蓝可以清理一块矩形的区域，从第 r1 行（含）到第 r2 行（含）的第 c1 列（含）到 c2 列（含）。
经过一段时间清理后，请问还有多少地方没有被清理过。
输入格式
输入第一行包含两个整数 n, m，用一个空格分隔。
第二行包含一个整数 t ，表示清理的次数。
接下来 t 行，每行四个整数 r1, c1, r2, c2，相邻整数之间用一个空格分隔，表示一次清理。请注意输入的顺序。
输出格式
输出一行包含一个整数，表示没有被清理过的面积。
样例输入
2 3
2
1 1 1 3
1 2 2 2
样例输出
2
样例输入
30 20
2
5 5 10 15
6 7 15 9
样例输出
519
评测用例规模与约定
对于所有评测用例，1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。
思路——常规版:通过给数组赋值，使用0或1来表示清理与未清理即可，推荐使用Arrays.fill()方法来填充数组。其中Arrays.fill()源码是通过for循环来给数组赋值的，那么这样做的时间复杂度是O(nmt) 也就是O(n³)，不过这道题范围小，一共也就是1e6，所以这样做也不会超时。
思路——优化版:给你两个点，修改矩阵部分区域的值 –> 二维差分，修改的时间复杂度是O(1)，还原的时间复杂度是O(n²)，总体时间复杂度为。O(n²)，从而降低了时间复杂度，虽然这道题不需要这么麻烦，不过还是练练吧。（这里直接上二维差分模板，由于矩阵的初值为默认值，这里就不需要进行初始化操作了。）
常规题解:import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main{ static int n, m, t; static int[][] map; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { String[] first = br.readLine().split(" "); n = Integer.parseInt(first[0]); m = Integer.parseInt(first[1]); map = new int[n][m]; t = Integer.parseInt(br.readLine()); for (int i = 0; i < t; i++) { String[] temp = br.readLine().split(" "); int r1 = Integer.parseInt(temp[0]); int c1 = Integer.parseInt(temp[1]); int r2 = Integer.parseInt(temp[2]); int c2 = Integer.parseInt(temp[3]); for (int j = r1 - 1; j <= r2 - 1; j++) { Arrays.fill(map[j], c1 - 1, c2, 1); } } int count = 0; for (int[] ints : map) { for (int anInt : ints) { if (anInt == 0) { count++; } } } System.out.println(count); }}
二维差分题解:import java.io.*;public class Main { final static int N = 110; static int n, m, t, res; static int[][] a = new int[N][N]; static int[][] d = new int[N][N]; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static void main(String[] args) { n = nextInt(); m = nextInt(); t = nextInt(); while (t-- > 0) insert(nextInt(), nextInt(), nextInt(), nextInt());//差分操作 //差分还原 a[1][1] = d[1][1];//第一格 for (int i = 2; i <= m; i++) a[1][i] = a[1][i - 1] + d[1][i];//第一行 for (int i = 2; i <= n; i++) a[i][1] = a[i - 1][1] + d[i][1];//第一列 for (int i = 2; i <= n; i++)//其余 for (int j = 2; j <= m; j++) a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] <= 0) res++; } } System.out.println(res); } static void insert(int x1, int y1, int x2, int y2) { d[x1][y1]++; d[x1][y2 + 1]--; d[x2 + 1][y1]--; d[x2 + 1][y2 + 1]++; } static int nextInt() { try { in.nextToken(); } catch (IOException e) { e.printStackTrace(); } return (int) in.nval; }}第九题【滑行距离】
问题描述
小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 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。
思路1（普通版——暴力搜索）:DFS找最长，用一个变量记录更新所有分支中的最大值。注意：回溯的时候把当前存储的滑行距离减一。
思路2（优化版——记忆化搜索）:作为一个学习者，我第一次做的时候只想到了暴力的dfs。前几天学习了一下数位dp，突然又想起来了这道题，有什么地方是我们当初忽略了的呢？让我再来捋一捋：回顾题目，我们可以看到这些字眼：
“从高到低”、“严格低于”、“任意位置开始滑行”，啊哈，我不知道你有没有感觉，关键就在于咱们对动态规划思想的敏感程度。按照动态规划的思想，咱们来推一把：较高位置的答案是由低的位置的答案推导过来的，此题的base情况就是最低位置自己，它自己不能向别处滑行，所以base情况为1。结合dfs：当我们搜到底的时候，也就找到了base，给它赋值为1，在回溯时，逐级递增，并用我们的备忘录dp[][] 来记录下对应位置的值。
解惑：为什么可以用dp呢？答：我们不确定的东西是什么？是搜索过程中后面的未知情况，而这些情况有规律可循，并且有着严格的单调性，当我们能够确定最底层时，前面的答案也就自然而然确定了，对于base情况，无论搜索多少次，结果都是一样，而由它推导出来的结果也必然具有唯一性，所以我们用备忘录dp来记录，这就是记忆化搜索。
普通dfs题解:import java.io.*;public class Main { static int n, m; static int max; static int[][] map; static int[][] dis = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static void main(String[] args) throws IOException { in.nextToken(); n = (int) in.nval; in.nextToken(); m = (int) in.nval; map = new int[n][m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { in.nextToken(); map[i][j] = (int) in.nval; } int res = 0; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[i].length; j++) { max = 0; dfs(i, j, 1); res = Math.max(res, max); } } System.out.println(res); } private static void dfs(int x, int y, int len) { for (int[] di : dis) { int dx = x + di[0]; int dy = y + di[1]; if (dx >= 0 && dx < n && dy >= 0 && dy < m && map[dx][dy] < map[x][y]) { len++; max = Math.max(max, len); dfs(dx, dy, len); len--; } } }}
记忆化搜索题解:import java.io.*;public class Main { static int[][] matrix, dp; static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; static int n, m; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(System.out); public static void main(String[] args) { n = nextInt(); m = nextInt(); matrix = new int[n][m]; dp = new int[n][m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) matrix[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(); } static int dfs(int x, int y) { if (dp[x][y] > 0) return dp[x][y];//如果该位置曾经通过base推导出来过，那么我们直接返回。 int ans = 1; for (int[] di : dir) { int dx = x + di[0]; int dy = y + di[1]; if (dx >= 0 && dy >= 0 && dx < n && dy < m && matrix[x][y] > matrix[dx][dy]) ans = Math.max(ans, dfs(dx, dy) + 1); } dp[x][y] = ans;//回溯时进行记录 return ans; } static int nextInt() { try { in.nextToken(); } catch (IOException e) { e.printStackTrace(); } 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[i] <= 10000。
对于所有评测用例，1 <= n <= 1000000，1 <= a[i] <= 1000000。
思路:注意看样例范围，对于百万级的数据，暴力求解的时间复杂度为O(n²)，必定超时，对于静态的区间最值问题考虑ST表，每次查询的时间复杂度是O（1），但是预处理的时间复杂度是O（nlogn）；单调队列的滑动窗口时间复杂度为O(n); 如果是动态问题，考虑使用线段树求解O（nlogn）。ST表题解
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main{ static int n, k, f; static int[] array; static int[][] ST; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { String fist = br.readLine(); n = Integer.parseInt(fist); f = (int) Math.ceil(Math.log(n) / Math.log(2)); array = new int[n]; ST = new int[n][f]; String[] second = br.readLine().split(" "); for (int i = 0; i < n; i++) array[i] = Integer.parseInt(second[i]); k = Integer.parseInt(br.readLine()); init(); for (int i = 0; i < n; i++) { int begin = Math.max(i - k, 0); int end = i + k < n ? i + k : n - 1; System.out.print(query(begin, end) + " "); } } static void init() { for (int i = 0; i < n; i++) { ST[i][0] = array[i]; } for (int k = 1; k < f; k++) { for (int s = 0; s + (1 << k) <= n; s++) { ST[s][k] = Math.min(ST[s][k - 1], ST[s + (1 << (k - 1))][k - 1]); } } } static int query(int begin, int end) { int len = end - begin + 1; int k = (int) (Math.log(len) / Math.log(2)); return Math.min(ST[begin][k], ST[end - (1 << k) + 1][k]); }}滑动窗口–单调队列 题解
（以i为中轴，把区间劈成两半，左边滑动一次，右边滑动一次，最后综合取最小，注意边界条件。不清楚数组模拟单调队列的同学可以看看我的这篇博客：单调队列（最高效版） ）
public class Main { static int N = (int) (1e6 + 10); static int n, k; static int[] a = new int[N]; static int[] q = new int[N]; static int[] l = new int[N]; static int[] r = new int[N]; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { n = nextInt(); for (int i = 0; i < n; i++) a[i] = nextInt(); k = nextInt();//找它左边的，包括它自己 int hh = 1, tt = 0; for (int i = 0; i < n; i++) { while (hh <= tt && a[q[tt]] > a[i]) tt--; q[++tt] = i; int left = Math.max(i - k, 0);//确定边界 if (q[tt] - q[hh] + 1 > i - left + 1) hh++; l[q[tt]] = a[q[hh]]; } //找它右边的，不包括它自己 hh = 1; tt = 0; for (int i = 0; i < n; i++) { while (hh <= tt && a[q[tt]] > a[i + 1]) tt--; q[++tt] = i + 1;//记住，是找右边的 int right = Math.min(i + k, n);//确定边界 if (q[tt] - q[hh] + 1 > right - i) hh++; if (q[hh] < n) r[q[tt] - 1] = a[q[hh]];//假如我们看了一下n（hh++），q[hh]变成了n，发现a[q[hh]]是0 ，不合法，所以要判断 else r[q[tt] - 1] = Integer.MAX_VALUE;//小坑：由于多开的数组部分默认值为0，直接沿用的话会对我们找最小产生影响，这里给它加个最大值来避免。 } for (int i = 0; i < n; i++) out.print(Math.min(r[i], l[i]) + " "); out.flush(); } static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; }}结语
题解全为本人手写，无抄袭，有些不完美，也可能有小错误，请大家批评指正。文章粗浅，希望对大家有帮助！