第十四届蓝桥杯大赛——真题训练第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;}
}