1.蓝桥杯(Java) -day01
2.蓝桥杯(Java) -day02
一、滑行
蓝桥杯-2023省赛模拟题-滑行
问题描述
小蓝准备在一个空旷的场地里面滑行,这个场地的高度不一,小蓝用一个 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)(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。
运行限制
解题思路
dp问题 比较简单,看注释
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int a[][];
static int n, m;
static boolean[][] visted;
static int[][] dfs;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();// 行
m = sc.nextInt();// 列
a = new int[n][m];
dfs = new int[n][m];
visted = new boolean[n][m];
for (int i = 0; i < n; i++) { // 输入
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
int count = 0;
//
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
count = Math.max(count, dfs(i, j));
}
}
System.out.println(count);
}
private static int dfs(int x, int y) {
// TODO Auto-generated method stub
if (visted[x][y] == true) {
return dfs[x][y];
}
visted[x][y] = true;
dfs[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] >= a[x][y]) {
continue; // 越界了或者值不满足
}
dfs[x][y] = Math.max(dfs[x][y], dfs(nx, ny) + 1);// 更新,返回当前位置的最长路径长度
}
return dfs[x][y];
}
}
二、滑行
蓝桥杯-2023省赛模拟题-星期几
问题描述
给定一天是一周中的哪天,请问 n 天后是一周中的哪天?
输入格式
输入第一行包含一个整数 w,表示给定的天是一周中的哪天,w 为 1 到 6 分别表示周一到周六,w 为 7 表示周日。
第二行包含一个整数 n。
输出格式
输出一行包含一个整数,表示 n 天后是一周中的哪天,1 到 6 分别表示周一到周六,7 表示周日。
样例输入
6
10
样例输出
2
评测用例规模与约定
对于所有评测用例,1 \leq n \leq 10000001≤n≤1000000。
运行限制
解题代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int date=sc.nextInt();
int add=sc.nextInt();
int next=((date+add)%7==0)?7:(date+add)%7;
System.out.println(next);
}
}
三、清理水域
蓝桥杯-2023省赛模拟题-清理水域
问题描述
小蓝有一个 n \times mn×m 大小的矩形水域,小蓝将这个水域划分为 nn 行 mm 列,行数从 11 到 nn 标号,列数从 11 到 mm 标号。每行和每列的宽度都是单位 11 。
现在,这个水域长满了水草,小蓝要清理水草。
每次,小蓝可以清理一块矩形的区域,从第 r1r1 行(含)到第 r2r2 行(含)的第 c1c1 列(含)到 c2c2 列(含)。
经过一段时间清理后,请问还有多少地方没有被清理过。
输入格式
输入第一行包含两个整数 n, mn,m,用一个空格分隔
第二行包含一个整数 tt ,表示清理的次数。
接下来 tt 行,每行四个整数 r1, c1, r2, c2r1,c1,r2,c2,相邻整数之间用一个空格分隔,表示一次清理。请注意输入的顺序。
输出格式
输出一行包含一个整数,表示没有被清理过的面积。
样例输入
2 3
2
1 1 1 3
1 2 2 2
样例输出
30 20
2
5 5 10 15
6 7 15 9
样例输出
519
运行限制
解题代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] glass = new int[n][m];
int t = sc.nextInt();// 次数
while (t-- > 0) {
int r1 = sc.nextInt()-1;
int c1 = sc.nextInt()-1;
int r2 = sc.nextInt()-1;
int c2 = sc.nextInt()-1;
for (int i = r1 ; i <=r2; i++) {
for (int j = c1 ; j <=c2; j++) {
if (glass[i][j] == 1) {
continue;
} else {
glass[i][j] = 1;}
}
}
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (glass[i][j] == 0) {
count++;
}
}
}
System.out.println(count);
}
}
四、附近最小
蓝桥杯-2023省赛模拟题-附近最小
这个题本人超时了,样例跑通了8/10
但是相对来说更加容易理解,可以用于参考
问题描述
小蓝有一个序列 a[1], a[2], …, a[n]a[1],a[2],…,a[n]。
给定一个正整数 kk,请问对于每一个 11 到 nn 之间的序号 ii,a[i-k], a[i-k+1], …, a[i+k]a[i−k],a[i−k+1],…,a[i+k] 这 2k+12k+1 个数中的最小值是多少?
当某个下标超过 11 到 nn 的范围时,数不存在,求最小值时只取存在的那些值。
输入格式
输入的第一行包含一整数 nn。
第二行包含 nn 个整数,分别表示 a[1], a[2], …, a[n]a[1],a[2],…,a[n]。
第三行包含一个整数 kk 。
输出格式
输出一行,包含 nn 个整数,分别表示对于每个序号求得的最小值。
样例输入
5
5 2 7 4 3
1
样例输出
2 2 2 3 3
解题代码
import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static long[] dp;
static int n;
static long[] m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = new long[n];
for (int i = 0; i < n; i++) {
m[i] = sc.nextInt();
}
int k = sc.nextInt();
dp = new long[n];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
dp[i] = Math.min(dp[i], dfs(k, i));
}
for (int i = 0; i < n; i++) {
System.out.print(dp[i] + " ");
}
sc.close();
}
static int t;
private static long dfs(int k, int i) {
// TODO Auto-generated method stub
long min = Integer.MAX_VALUE;
t = -k;
while (i + t <= i + k) {
if (i + t < 0 || i + t >= n) {
t++;
continue;
} else {
min = Math.min(min, m[i + t]);
t++;
}
}
return min;
}
}
五、最大连通
蓝桥杯-2023省赛模拟题-最大连通
很尴尬这个题,超内存了,但因为是填空题,所以影响不大
问题描述
小蓝有一个 30 行 60 列的数字矩阵,矩阵中的每个数都是 0 或 1 。
110010000011111110101001001001101010111011011011101001111110
010000000001010001101100000010010110001111100010101100011110
001011101000100011111111111010000010010101010111001000010100
101100001101011101101011011001000110111111010000000110110000
010101100100010000111000100111100110001110111101010011001011
010011011010011110111101111001001001010111110001101000100011
101001011000110100001101011000000110110110100100110111101011
101111000000101000111001100010110000100110001001000101011001
001110111010001011110000001111100001010101001110011010101110
001010101000110001011111001010111111100110000011011111101010
011111100011001110100101001011110011000101011000100111001011
011010001101011110011011111010111110010100101000110111010110
001110000111100100101110001011101010001100010111110111011011
111100001000001100010110101100111001001111100100110000001101
001110010000000111011110000011000010101000111000000110101101
100100011101011111001101001010011111110010111101000010000111
110010100110101100001101111101010011000110101100000110001010
110101101100001110000100010001001010100010110100100001000011
100100000100001101010101001101000101101000000101111110001010
101101011010101000111110110000110100000010011111111100110010
101111000100000100011000010001011111001010010001010110001010
001010001110101010000100010011101001010101101101010111100101
001111110000101100010111111100000100101010000001011101100001
101011110010000010010110000100001010011111100011011000110010
011110010100011101100101111101000001011100001011010001110011
000101000101000010010010110111000010101111001101100110011100
100011100110011111000110011001111100001110110111001001000111
111011000110001000110111011001011110010010010110101000011111
011110011110110110011011001011010000100100101010110000010011
010011110011100101010101111010001001001111101111101110011101
如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置,则称两个位置连通。与某一个标为 1 的位置连通的所有位置(包括自己)组成一个连通分块。
请问矩阵中最大的连通分块有多大?
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
运行限制
最大运行时间:1s
最大运行内存: 256M
解题思路
这个题是dp变形问题,需要把各条支路上的数加上
解题代码
import java.util.Scanner;
public class Main {
static int[][] dp = new int[30][61];
static char[][] a = new char[30][61];
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 30; i++) {
a[i] = sc.next().toCharArray();
}
int count = 0;
for (int i = 0; i < 30; i++) {
for (int j = 0; j < 60; j++) {
if (a[i][j] == '1') {
count = Math.max(count, dfs(i, j));
}
}
}
System.out.println(count);
}
private static int dfs(int x, int y) {
// TODO Auto-generated method stub
if (x < 0 || x >= 30 || y < 0 || y >= 60 || a[x][y] != '1') {
return 0;
}
a[x][y] = '2';
int count = 1;
count += dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
return count;
}
}
列名
蓝桥杯-2023省赛模拟题-列名
问题描述
在 Excel 中,列的名称使用英文字母的组合。前 2626 列用一个字母,依次为 AA 到 ZZ,接下来 26\times 2626×26 列使用两个字母的组合,依次为 AAAA 到 ZZZZ。
请问第 20222022 列的名称是什么?
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串,在提交答案时只填写这个字符串,填写多余的内容将无法得分。
运行限制
填空题哦,应该手算也能算出来
解题代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
int num=2022;
String s="";
while(num>0) {
s=(char)(num%26-1+'A')+s;
num/=26;
}
System.out.println(s);
}
}