第十四届蓝桥杯校内模拟赛（第三期）Java组题解分享

文章 目录

填空题
编程题

本篇文章中的题解是我在比赛中的思路或者所写的代码, 总结出的一篇相对来说比较清晰的个人题解, 希望要备战蓝桥杯的小伙伴能够看到最后(注意：本次Jav a组和C++组的题目不一样，本文所写的题目均为Jav a组的)~

编程题

一周第几天

问题描述：给定一天是一周中的哪天，请问 n 天后是一周中的哪天？
输入格式
　　输入第一行包含一个整数 w，表示给定的天是一周中的哪天，w 为 1 到 6 分别表示周一到周六，w 为 7 表示周日。
　　第二行包含一个整数 n。
输出格式
　　输出一行包含一个整数，表示 n 天后是一周中的哪天，1 到 6 分别表示周一到周六，7 表示周日。
样例输入
6
10
样例输出
2
评测用例规模与约定
　　对于所有评测用例，1 <= n <= 1000000。

思路：直接+n天之后模7就可以得到最终是星期几，但是有一个需要注意，如果结果是0，需要将其手动变为7即可。

Java 代码：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int n = scanner.nextInt();
        int res = (w + n) % 7;
        if(res == 0) res = 7;
        System.out.println(res);
    }
}

被覆盖的点

问题描述：小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 (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。

思路：由于这道题的数据量比较小，我们可以先把所有信号塔的坐标都存起来，之后暴力地遍历整块区域中的所有点，判断该点到所有信号塔的距离是否有在半径的范围之内，如果存在其中，则结果++。值得注意的是，如果只是单纯执行上述的步骤，答案是错的，因为有可能会有一个点计算两次的情况，因此我们需要额外的一个数组来存当前点是否已经存在过了，如果之前就已经加过了，那么久不需要再执行此操作。

Java 代码：

import java.util.*;

class Pair{
    public int x;
    public int y;
    
    public Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main{
    public static boolean[][] st = new boolean[110][110];
    
    public static boolean check(int i, int j, Pair pair, int r){
        int x = pair.x;
        int y = pair.y;
        if((x - i) * (x - i) + (y - j) * (y - j) <= r * r){
            st[i][j] = true;
            return true;
        }
        return false;
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();
        int n = scanner.nextInt();
        int r = scanner.nextInt();
        List<Pair> list = new ArrayList<>();
        while(n-- > 0){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            list.add(new Pair(x, y));
        }
        int res = 0;
        for(int i = 0; i <= w; i++){
            for(int j = 0; j <= h; j++){
                for(int k = 0; k < list.size(); k++){
                    if(st[i][j] == false && check(i, j, list.get(k), r)) res++;
                }
            }
        }
        System.out.println(res);
    }
}

未被清理的区域

问题描述：小蓝有一个 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。

思路：如果你做过差分类型的题目，这道题其实一眼就可以看出来是差分思想，虽然说这道题数据量不大，但是是一个二维矩阵，直接使用暴力的做法可能会超时，因此我们存的是一个差分矩阵，最后再使用一遍前缀和就可以会快解出这道题了。

Java 代码：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int t = scanner.nextInt();
        int[][] a = new int[n + 10][m + 10];
        while(t-- > 0){
            int r1 = scanner.nextInt();
            int c1 = scanner.nextInt();
            int r2 = scanner.nextInt();
            int c2 = scanner.nextInt();
            a[r1][c1]++;
            a[r2 + 1][c1]--;
            a[r1][c2 + 1]--;
            a[r2 + 1][c2 + 1]++;
        }
        int res = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
                if(a[i][j] == 0) res++;
            }
        }
        System.out.println(res);
    }
}

滑行距离

问题描述：小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 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之后还需要进行一下回溯即可。

Java 代码：

import java.util.*;

public class Main{
    public static int[] getX = {0, 1, 0, -1};
    public static int[] getY = {1, 0, -1, 0};
    
    public static int cnt = 0;
    
    public static void dfs(int[][] h, int x, int y, int n, int m, int l){
        for(int i = 0; i < 4; i++){
            int newx = x + getX[i];
            int newy = y + getY[i];
            if(newx >= 0 && newx < n && newy >= 0 && newy < m && h[newx][newy] < h[x][y]){
                l++;
                cnt = Math.max(cnt, l);
                dfs(h, newx, newy, n, m, l);
                l--;
            }
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] h = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                h[i][j] = scanner.nextInt();
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cnt = 0;
                dfs(h, i, j, n, m, 1);
                res = Math.max(res, cnt);
            }
        }
        System.out.println(res);
    }
}

区间 最小值

问题描述：小蓝有一个序列 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)或一下，O(nlogn)可能还是有点悬。单调队列其实就是一个滑动窗口，详细一点来说就是一个知道当前窗口中最大或者最小值的一个可以滑动等长子序列。
而这道题要求的是一个元素从左边k个位置开始到右边k个位置这段区间的最小值，所以我们可以使用两个滑动窗口，一个从前往后遍历（求出当前位置之前的k个元素的最小值），另外一个从后往前遍历（求出当前位置之后的k个元素的最小值），最后每个元素上的最小值就是两个单调队列在该位置上的较小值，即为该元素从左边k个位置开始到右边k个位置这段区间的最小值。

Java代码：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) a[i] = scanner.nextInt();
        int k = scanner.nextInt();
        int[] q1 = new int[n];
        int[] q2 = new int[n];
        int[] res = new int[n];
        int hh = 0, tt = -1;
        for(int i = 0; i < n; i++){
            if(hh <= tt && q1[hh] < i - k) hh++;
            while(hh <= tt && a[q1[tt]] >= a[i]) tt--;
            q1[++tt] = i;
            res[i] = a[q1[hh]];
        }
        hh = 0;
        tt = -1;
        for(int i = n - 1; i >= 0; i--){
            if(hh <= tt && q2[hh] > i + k) hh++;
            while(hh <= tt && a[q2[tt]] >= a[i]) tt--;
            q2[++tt] = i;
            res[i] = Math.min(res[i], a[q2[hh]]);
        }
        for(int i = 0; i < n; i++){
            System.out.print(res[i] + " ");
        }
    }
}