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

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

B、Excel表格组合

C、求满足条件的日期

D、取数字 - 二分

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;i1;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
		{
			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
		{
			String s=sc.next();
			for(int j=0;j'0';
		}
			
		int res=0;
		for(int i=0;i
		{
			for(int j=0;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 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=0&&ny0&&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
		{
			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 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
          for(int j=0;j
        
        for(int i=0;i
          for(int j=0;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=0&&ny
        {
          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
          for(int j=0;j
        
        for(int i=0;i
          for(int j=0;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=0&&ny
        {
          d[x][y]=Math.max(d[x][y],dfs(nx,ny)+1);
        }
      }
      return d[x][y];
 
    }
}

相关阅读:
数字IC秋招-基础/SOC/计算机体系结构
 模板学堂丨JumpServer安全运维审计大屏
 【计算机视觉】Graph Models算法介绍合集（四）
Hive 基本操作
 C#完成XML文档节点的自动计算功能
 Odoo16—权限控制
 MVVM的构建（java&kotlin）
看一遍学会Vue结合axios使用mockjs
高并发缓存策略大揭秘：面试必备的缓存更新模式解析
 Cannot read properties of null (reading ‘insertBefore‘)
原文地址：https://blog.csdn.net/weixin_61639349/article/details/134447019

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

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%）

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

D、取数字 - 二分

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