【蓝桥杯第十五届模拟赛 Java B组】训练题（A

A、求全是字母的最小十六进制数

B、Excel表格组合

C、求满足条件的日期

D、取数字 - 二分

（1）暴力

（2）二分

E、最大连通块 - bfs

F、哪一天？

G、信号覆盖 - bfs

（1）bfs（60%）

（2）暴力

H、清理水域 - 暴力（弱智版）可以差分

I、滑行 - dfs + dp

（1）dfs（30%）

（2）dp+dfs（100%）

A、求全是字母的最小十六进制数

请找到一个大于2022的最小数，该数转换为十六进制后，所有数位（不含前导0）都为字母（A到F），请计算出这个数的十进制。

思路：

最小的全是字母的数肯定是全是a的，从2023开始逐个循环转十六进制判断即可

答案：2730

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=2023;while(true){String s=Integer.toHexString(n);if(ck(s)==true) break;n++;}System.out.print(n);}public static boolean ck(String s){for(char c:s.toCharArray()){if(c<'a'||c>'f') return false;}return true;}
}

B、Excel表格组合

在Excel中，列的名称使用英文字母组合，前26列用一个字母，依次为A到Z，接下来26*26列使用两个字母的组合，依次为AA到ZZ，求第2022列的名称是什么？

思路：

已知单个字母和双字母组合共26+26*26=702，而三个字母组合有26*26*26=17576，因此第2022列名称为三个字母的组合

三重暴力算2022列的值，答案为：BYT

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int beg=702;for(int i=0;i<26;i++)for(int j=0;j<26;j++)for(int k=0;k<26;k++){beg++;if(beg==2022){char a=(char)('A'+i),b=(char)('A'+j),c=(char)('A'+k);System.out.print(a+" "+b+" "+c);break;}}}
}

C、求满足条件的日期

对一个日期，我们可以计算出年份的各个数位上的数字之和，也可以分别计算月和日的各位数字之和。请问从1900年1月1日至9999年12月31日，总共有多少天，年份的数位数字之和=月的数位之和+日的数位之和。

例如：2022年11月13日满足要求，因为6=2+4

请求出满足条件的日期总数量

思路：

数组记录1——12月每一个月的天数，注意闰年2月为29天，然后三重暴力循环计算即可

答案：70910

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int res=0;int[] a= {0,31,28,31,30,31,30,31,31,30,31,30,31};for(int i=1900;i<=9999;i++){String y=String.valueOf(i);for(int j=1;j<=12;j++){if(i%400==0||(i%4==0&&i%100!=0)) a[2]=29;else a[2]=28;String m=String.valueOf(j);for(int k=1;k<=a[j];k++){String d=String.valueOf(k);if(ck(y,m,d)) res++;}}}System.out.print(res);}public static boolean ck(String y,String m,String d){int yy=0,mm_dd=0;for(char c:y.toCharArray()) yy+=c-'0';for(char c:m.toCharArray()) mm_dd+=c-'0';for(char c:d.toCharArray()) mm_dd+=c-'0';if(yy==mm_dd) return true;return false;}

D、取数字 - 二分

小蓝有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？

思路：

直接暴力枚举，二分优化，答案是：189

（1）暴力

public class Main4 {public static void main(String[] args) {int res=0;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};for(int i=0;i<30;i++)for(int j=i+1;j<30;j++ ) if(a[i]*a[j]>=2022) res++;System.out.println(res);}
}

（2）二分

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int res=0;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};Arrays.sort(a);for(int i=0;i<a.length-1;i++)  //最后一个数没有后续配对的{int target=(int)Math.ceil(2022*1.0/a[i]);int idx=binary(a,target,i+1,a.length-1); //在【i+1,n-1】区间找防止重复if(2022/a[i]>a[idx]) continue;res+=a.length-idx;}System.out.print(res);}public static int binary(int[] a,int target,int l,int r){while(l<r){int mid=l+r>>1;if(a[mid]>=target) r=mid;else l=mid+1;}return r;}
}

E、最大连通块 - bfs

小蓝有一个 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 的位置连通的所有位置（包括自己）组成一个连通分块。　　

请问矩阵中最大的连通分块有多大？

思路：

答案是148

bfs进入为1的点，上下左右扩展计数，最后求每一次bfs最大值即可，模板提

import java.util.*;public class abc {static int n=30,m=60;static int[][] g=new int[n][m];static int[][] st=new int[n][m];static int[] dx={0,0,1,-1},dy= {1,-1,0,0};public static void main(String[] args){Scanner sc=new Scanner(System.in);String t;for(int i=0;i<n;i++){String s=sc.next();for(int j=0;j<m;j++) g[i][j]=s.charAt(j)-'0';}int res=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(g[i][j]==1&&st[i][j]==0)res=Math.max(res, bfs(i,j));}}System.out.print(res);}public static int bfs(int x,int y){int cnt=1;st[x][y]=1;Queue<PII> q=new LinkedList<>();q.offer(new PII(x,y));while(!q.isEmpty()){PII t=q.poll();int xx=t.x,yy=t.y;for(int i=0;i<4;i++){int nx=dx[i]+xx,ny=dy[i]+yy;if(nx>=0&&nx<n&&ny>=0&&ny<m&&st[nx][ny]==0&&g[nx][ny]==1){st[nx][ny]=1;q.offer(new PII(nx,ny));cnt++;}}}return cnt;}}
class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}

F、哪一天？

1<=n<=10^6

思路：

注意特判整除7的情况，不能输出0，应该输出7

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int w=sc.nextInt(),n=sc.nextInt();int res=(w+n%7)%7;System.out.print(res==0? 7:res);}
}

G、信号覆盖 - bfs

问题描述

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

（1）bfs（60%）

can you tell me why？

思路：

st数组标记被覆盖的坐标点，对于每个信号塔进行bfs，对每个点上下左右扩展

若【在合法范围内】且【未标记】且【该点到信号塔的距离<=r】，则入队标记，并统计覆盖点范围

import java.util.*;public class abc {static int[][] st;static int res=0,r,h,w,n;static int[] dx={0,0,1,-1},dy= {1,-1,0,0};public static void main(String[] args){Scanner sc=new Scanner(System.in);w=sc.nextInt();h=sc.nextInt();n=sc.nextInt();r=sc.nextInt();st=new int[w+1][h+1];for(int i=0;i<n;i++){int x=sc.nextInt(),y=sc.nextInt();bfs(x,y);}for(int i=0;i<=w;i++)for(int j=0;j<=h;j++) if(st[i][j]==1) res++;System.out.print(res);}public static void bfs(int x,int y){st[x][y]=1;Queue<PII> q=new LinkedList<>();q.offer(new PII(x,y));while(!q.isEmpty()){PII t=q.poll();int xx=t.x,yy=t.y;for(int i=0;i<4;i++){int nx=dx[i]+xx,ny=dy[i]+yy;if(nx>=0&&nx<=w&&ny>=0&&ny<=h&&st[nx][ny]==0&&ck(x,y,nx,ny)){q.offer(new PII(nx,ny));st[nx][ny]=1;}}}}public static boolean ck(int x,int y,int nx,int ny){int dis=(x-nx)*(x-nx)+(y-ny)*(y-ny);if(dis<=r*r) return true;return false;}
}
class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}

（2）暴力

import java.util.*;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int w = scan.nextInt(), h = scan.nextInt(), n = scan.nextInt(), r = scan.nextInt();int[][] arr = new int[n][2];for (int i = 0; i < n; i++) {arr[i][0] = scan.nextInt();arr[i][1] = scan.nextInt();}int count = 0;for (int i = 0; i <= w; i++) {for (int j = 0; j <= h; j++) {if (check(arr, n, r, i, j)) {count++;}}}System.out.println(count);}public static boolean check(int[][] arr, int n, int r, int x, int y) {for (int i = 0; i < n; i++) {int x0 = x - arr[i][0];int y0 = y - arr[i][1];if (x0 * x0 + y0 * y0 <= r * r) return true;}return false;}
}

H、清理水域 - 暴力（弱智版）可以差分

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt(),t=sc.nextInt();int[][] g=new int[n+1][m+1];int res=0;while(t-->0){int r1=sc.nextInt(),c1=sc.nextInt(),r2=sc.nextInt(),c2=sc.nextInt();for(int i=r1;i<=r2;i++)for(int j=c1;j<=c2;j++) g[i][j]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) if(g[i][j]==0) res++;System.out.print(res);}}

I、滑行 - dfs + dp

输入格式
　　输入第一行包含两个整数 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（30%）

import java.util.*;
import java.math.*;public class Main {static int res=0;static int[] dx={0,0,1,-1},dy={1,-1,0,0};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();int[][] g=new int[n][m];for(int i=0;i<n;i++)for(int j=0;j<m;j++) g[i][j]=sc.nextInt();for(int i=0;i<n;i++)for(int j=0;j<m;j++){dfs(i,j,g,1,n,m);}System.out.print(res);sc.close();}public static int dfs(int x,int y,int[][] g,int cnt,int n,int m){for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]<g[x][y]){cnt++;res=Math.max(res,cnt);dfs(nx,ny,g,cnt,n,m);cnt--;}}return cnt;}
}

（2）dp+dfs（100%）

思路：

定义d[i][j]为从（i，j）出发能滑行的最长距离，则求出max每个d[i][j]即可

import java.util.*;
import java.math.*;public class Main {static int n,m,res=0;static int[][] g,d;static int[] dx={0,0,1,-1},dy={1,-1,0,0};public static void main(String[] args) {Scanner sc = new Scanner(System.in);n=sc.nextInt();m=sc.nextInt();g=new int[n][m];d=new int[n][m];for(int i=0;i<n;i++)for(int j=0;j<m;j++) {g[i][j]=sc.nextInt();}for(int i=0;i<n;i++)for(int j=0;j<m;j++)res=Math.max(res,dfs(i,j));System.out.print(res);sc.close();}public static int dfs(int x,int y){if(d[x][y]!=0) return d[x][y]; //如果这个点被访问过，返回从这个点能滑行的最大距离d[x][y]=1;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]<g[x][y]){d[x][y]=Math.max(d[x][y],dfs(nx,ny)+1);}}return d[x][y];}
}