目录
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];
}
}
