蓝桥杯2022省赛总结

试题 E: 求阶乘

时间限制: 1.0 s 内存限制: 512.0 MB  本题总分：15 分

【问题描述】

  满足 N ! 的末尾恰好有 K个 0 的最小的 N 是多少?

  如果这样的 N 不存在输出 − 1 。

【输入格式】

  一个整数 K。

【输出格式】

  一个整数代表答案。

【样例输入】

  2

【样例输出】
  10

【评测用例规模与约定】

  对于 30 % 的数据，1 ≤ K ≤ 10  1 ≤ K ≤ 10^6 
  对于 100 % 的数据，1 ≤ K ≤ 10 ^18

 🌙 个人思路:(看了包会)

        这题跟百度以前的面试题有点像(1...100!有几个0),但这题要反推 ,他要求刚好有k个0的N!中N

的最小值,那么0是由乘以10所得到的,那么10又是怎么来的呢?是由2*5得到的对吧=>那么这道题的

就可以转化为1..N的阶乘谁能贡献出2和5,2是由 0 2 4 6 8来的所以能出5 必然有2 所以2 一定是够

用的 那么问题就是能产生5的数了 能产生5的数 有5 25 125 那么我们只要统计好 有几个数能产生5

就好了。现在目标是产生k个0的最小数,那么可以从小往大递推,比如2个0可以由两个5的因数构成

,也可以由因数为25的数构成,那么我们可以以5为增率递加数据,判断新得到的数字能贡献几个5就可

以了.（再优化的方法要用二分，单纯写只有35分）

        那么在这里讲一下优化后的算法,首先上次分析得来的我们只要找的N的因数5就好了,那么有几

个呢,观察可以发现最多有K个,那么我们不妨控制答案范围在[1,nk]区间中,那么此时就可以结合二分

查找的思想快速找到答案

import java.util.Scanner;

public class Main {
		public static void main(String[] args){
			Scanner sr = new Scanner(System.in);
			long K = sr.nextLong();//输入数据
			//从小到大递推过来 以5为单位递增
			int ans =0;//用ans记录能贡献几个5
			for(long i=5;;i+=5){
				ans+=check(i);//判断i能贡献多少个5
				if(ans>K){
					System.out.print(-1);
					return;
				}else if(ans==K){
					System.out.print(i);
					return;
				}
			}
		}

		private static int check(long x) {
			// TODO Auto-generated method stub
			int k =0;
			for(int i=5;;i*=5){
				if(x%i==0){
					k++;
				}else{
					break;
				}
			}
			return k;
		}
	}		

试题 F: 最大子矩阵

时间限制: 1.0 s  内存限制: 512.0 MB 本题总分：15 分

【问题描述】

  小明有一个大小为 N × M的矩阵，可以理解为一个 N行 M 列的二维数组。我们定义一个矩阵 m的稳定度 f ( m ) 为 f ( m ) = max ⁡ ( m ) − min ⁡ ( m ) ，其中 max ⁡ ( m ) 表示矩阵 m中的最大值，min ⁡ ( m ) 表示矩阵 m中的最小值。现在小明想要从这个矩阵中找到一个稳定度不大于 limit的子矩阵，同时他还希望这个子矩阵的面积越大越好（面积可以理解为矩阵中元素个数）。

  子矩阵定义如下：从原矩阵中选择一组连续的行和一组连续的列，这些行列交点上的元素组成的矩阵即为一个子矩阵。

【输入格式】

  第一行输入两个整数 N ,M表示矩阵的大小。

  接下来 N行，每行输入 M个整数，表示这个矩阵。

  最后一行输入一个整数 limit，表示限制。

【输出格式】

  输出一个整数，分别表示小明选择的子矩阵的最大面积。

【样例输入】

   3   4

   2   0   7  9

   0   6   9  3

   8   3   6  4

   8

【样例输出】

  6

 【样例说明】
  满足稳定度不大于 8 的且面积最大的子矩阵总共有三个，他们的面积都是 6 (粗体表示子矩阵元素):

  2   0   7   9 
  0   6   9   7 
  8   4   6   4 

  2   0   7   9 
  0   6   9   7 
  8   4   6   4 

  2   0   7   9

       0   6 9   7 
  8   4   6   4 

【评测用例规模与约定】

        

对于所有评测用例,0≤ 矩阵元素值，limit ≤ 10^5

 .......等我有时间了再更新,这题我是用暴力做的,只有35分