第十四届蓝桥杯大赛——真题训练第10天
目录
第一题：扫雷
题目描述
输入描述
输出描述
输入输出样例
运行限制
题目代码
第 2 题：完全平方数
问题描述
输入格式
输出格式
样例输入 1
样例输出 1
样例输入 2
样例输出 2
题目分析
题目代码
第三题：求阶乘
问题描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定
题目分析
题目代码
第一题：扫雷
题目描述
在一个 n 行 m 列的方格图上有一些位置有地雷，另外一些位置为空。
请为每个空位置标一个整数，表示周围八个相邻的方格中有多少个地雷。
输入描述
输入的第一行包含两个整数 n,m。
第 22 行到第 n+1 行每行包含 m 个整数，相邻整数之间用一个空格分隔。如果对应的整数为 00，表示这一格没有地雷。如果对应的整数为 11，表示这一格有地雷。
其中，1≤n,m≤100 分钟后还是在当天。
输出描述
输出 n 行，每行 m 个整数，相邻整数之间用空格分隔。
对于没有地雷的方格，输出这格周围的地雷数量。对于有地雷的方格，输出 99。
输入输出样例
示例 1
输入
3 4 0 1 0 0 1 0 1 0 0 0 1 0输出
2 9 2 1 9 4 9 2 1 3 9 2运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
题目代码
import java.util.Scanner;public class 扫雷 {public static void main(String[] args) {Scanner sca = new Scanner(System.in);int n = sca.nextInt();int m = sca.nextInt();sca.nextLine();String[][] arr = new String[n][m];for (int i = 0; i < n; i++) {arr[i] = sca.nextLine().split(" ");}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (arr[i][j].equals("1")) {System.out.print("9" + " ");} else {int count = 0;//同一行if (j-1>=0&&arr[i][j-1].equals("1")){count++;}if (j+1<m&&arr[i][j+1].equals("1")){count++;}//上一行if (i-1>=0&&arr[i-1][j].equals("1")){count++;}if (i-1>=0&&j-1>=0&&arr[i-1][j-1].equals("1")){count++;}if (i-1>=0&&j+1<m&&arr[i-1][j+1].equals("1")){count++;}//下一行if (i+1<n&&arr[i+1][j].equals("1")){count++;}if (i+1<n&&j-1>=0&&arr[i+1][j-1].equals("1")){count++;}if (i+1<n&&j+1<m&&arr[i+1][j+1].equals("1")){count++;}System.out.print(count+" ");}}System.out.println();}} }
第 2 题：完全平方数
问题描述
一个整数 a 是一个完全平方数, 是指它是某一个整数的平方, 即存在一个 整数 b, 使得 2a=b2 。
给定一个正整数 n, 请找到最小的正整数 x, 使得它们的乘积是一个完全平 方数。
输入格式
输入一行包含一个正整数 n 。
输出格式
输出找到的最小的正整数 x 。
样例输入 1
12
样例输出 1
3
样例输入 2
15
样例输出 2
15
题目分析
(1)找一个x使得x*n为一个平方数
(2)注意数据范围要用long
(3)如何找出这个最小数x呢,如果n是由a*a*b*b.....*y(y为不能开方的数)组成的话
(4)那我们是不是最后只需要把y赋值给x，就可以保证x*n是完全平方数了
参考链接：https://blog.csdn.net/m0_55858611/article/details/129765554
题目代码
import java.util.Scanner;/*** 1、找一个x使得x*n为一个平方数* 2、注意数据类型要用long* 3、如何找出这个最小数x呢,如果n是由a*a*b*b.....*y(y为不能开方的数)组成的话* 4、那我们是不是把x赋值为y，就可以保证n是完全平方数了,其中a、b都是小于等于sqrt(n)的*/ public class 完全平方数 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);long n = scan.nextLong();//正整数nlong res = 0L;//最小正整数for (Long i = 1L; i * i <= n; i++) { // i^2 <= n//如果这个n由(i*i)^k组成，就一直除到它没有i的平方为止if (n % (i * i) == 0) {// n % i^2res = n / (i * i);//每次都维护值是越来越小的}}System.out.print(res);scan.close();} }
第三题：求阶乘
问题描述
满足 N ! 的末尾恰好有 K 个 0 的最小的 N 是多少?
如果这样的 N 不存在输出 −1−1 。
输入格式
一个整数 K 。
输出格式
一个整数代表答案。
样例输入
2样例输出
10评测用例规模与约定
对于 30%30% 的数据, 1≤�≤1061≤K≤106.
对于 100%100% 的数据, 1≤�≤10181≤K≤1018.
题目分析
1）直接算 N! 很难。N! 末尾的 0 取决于1 到 N 中因子 2 和 5的组合个数，实际取决于 5 的个数，因为 5 的倍数个数永远少于 2 的，所以可以统计 1 到 N 中 5 的倍数个数 。
/*
输入一个正整数N,求N!(N的阶乘)末尾有多少个0？
例如
5! = 120,0的个数为1
10! = 3628800,0的个数为2
25! = 15511210043330985984000000,0的个数为6
*//*
算法逻辑：
要判断末尾有几个0就是判断可以整除几次10，
10的因子有5和2，而在0~9之间5的倍数只有一个，2的倍数相对较多，
即转换成了求N阶乘中有几个5的倍数。
*/2）最后用二分来找n
参考原文链接：https://blog.csdn.net/Zhangyanfeng1/article/details/107253252
题目代码
import java.util.Scanner;public class 求阶乘 {public static void main(String[] args) {Scanner sca = new Scanner(System.in);long k = sca.nextLong();long left = 1;long right = (long) 9e18;long res = 0;//二分查找while (left <= right) {long mid = left + (right - left) / 2;if (find_5(mid) < k) {res = mid;left = mid + 1;} else {right = mid - 1;}}if (find_5(res + 1) == k) {System.out.println(res + 1);} else System.out.println(-1);}//为什么要循环除5呢？/*我们举一个例子: n=100时(1) n/5=20;表示在1~n有20个区间大小为5的区间(5只能分解一个5)(2) (n/5)/5=4;表示在1~n有4个区间大小为25的区间(25可以分解两个5)(3)((n/5)/5)/5=0;表示1~n有0个区间大小为125的区间(125可以分解3个5)*/static long find_5(long n) {//找5的倍数的个数long res = 0l;while (n / 5 != 0) {res += n / 5;n = n / 5;}return res;} }