个人名片：
🐼作者简介：一名大二在校生，喜欢编程🎋
🐻❄️个人主页🥇：小新爱学习.
🐼个人WeChat：hmmwx53
🕊️系列专栏：🖼️
- 零基础学Java——小白入门必备
- 重识C语言——复习回顾
- 计算机网络体系———深度详讲
- 微信小程序开发——实战开发
🐓每日一句：🍭我很忙，但我要忙的有意义！
文章目录
- 第十四届蓝桥杯全国软件和信息技术专业人才大赛
- 蓝桥杯大赛介绍
- 试题 E: 求阶乘
- 试题 F: 最大子矩阵
- 试题 G: 数组切分
- 持续更新........🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇
- 欢迎添加微信，加入我的核心小队，请备注来意
第十四届蓝桥杯全国软件和信息技术专业人才大赛
蓝桥杯大赛介绍
蓝桥杯全国软件和信息技术专业人才大赛是全国性的IT类学科赛事。连续三年入选中国高等教育学会发布的“全国普通高校学科竞赛排行榜”，是高校教育教学改革和创新人才培养的重要竞赛项目。十三年来，吸引北京大学、清华大学、复旦大学、上海交通大学、中国科学技术大学等1600余所高校，累计超过65万余名选手参赛。
试题 E: 求阶乘
【问题描述】
满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?
如果这样的 N 不存在输出 −1。
【输入格式】
一个整数 K。
【输出格式】
一个整数代表答案。
【样例输入】
2
【样例输出】
10
【评测用例规模与约定】
对于 30% 的数据，1 ≤ K ≤ 10……6.
对于 100% 的数据，1 ≤ K ≤ 10……18
【题解思路】
分析题可知这道题也可以使用暴力法，但可能会通过不了。因为末尾有k个0，末尾有0就是要凑10，而只有25,才能得到10，所以阶乘中2的个数远远大于5，所以要凑5，注意对于25,125等数字其中包含不止一个5，所以不能直接输出5K，当k为5时，25的阶乘末尾有6个0，暴力求解：
import java.util.Scanner;
public class Main {//后面以0 结尾的一定是5！....(5的倍数的阶乘) 所以只需要判断5的倍数的阶乘//(判断的数)/5 就是含有5的个数 也是阶乘后0的个数public static void main(String[] args) {Scanner sc = new Scanner(System.in);long k = sc.nextLong();long count;long a = 5;//直接从5的阶乘(120)开始判断while (true) {long tempA = a;count = 0;while (tempA > 0) {tempA /= 5;count += tempA;}if (count < k) {a += 5;} else if (count == k) {System.out.println(a);break;} else {System.out.println(-1);break;}}}
}
也不能直接从1到N枚举判断，突破口是数字中谁和谁相乘得到10，很容易想到2*5，2的个数肯定比5多，所以N的阶乘最后有多少0 就看N能分成多少5 。可以从1~N每个数都除以5，然后统计个5的个数，因为25/5也会得到5，所以需要用循环计算。那就用到二分求解：
//因为k的值很大 不可能用枚举的思想依次对k比较
//我们先测一下 Long.MAX_VALUE的阶乘后边有多少个0
//Long.MAX_VALUE的阶乘后边有 2305843009213693937个0(10的19次方) > k
//Long.MAX_VALUE/2的阶乘后边有 1152921504606846964个0(10的19次方) > k
(所有在使用二分法时 有边界是Long.MAX_VALUE-5 左边界是1 不会有溢出)
//因为N的阶乘后边有k个0 这个k随N的增大而增大 所以我们用二分查找
//对于 100% 的数据，1 ≤ K ≤ 10的18次方
//把l = 1作为最左边 r = Long.MAX_VALUE - 5;做为最右边
import java.util.Scanner;public class Main {// 求x的阶乘后边有多少个0static long calc(long x){long res = 0;while (x!=0){res = res+x/5;x/=5;}return res;}//static void solve() {//第1部分代码//System.out.print(calc(10));//计算10的阶乘是不是后边有2个0//System.out.print(calc(25));//计算25的阶乘是不是后边有6个0//第2部分代码//System.out.print(calc(Long.MAX_VALUE/2 ));//Long.MAX_VALUE的阶乘后边有 2305843009213693937个0//Long.MAX_VALUE/2的阶乘后边有 1152921504606846964个0//二分查找Scanner scanner = new Scanner(System.in);long k = scanner.nextLong();long l = 1, r = Long.MAX_VALUE - 5;//l为最左边 r为最右边//long l = 1, r = 20;//方便学习可以debugwhile (l < r) {long mid = (l + r) / 2;if (k <= calc(mid)) {//如果mid的阶乘的0数大于等于kr = mid;//我们让r变为mid (可以等于mid)} else {//如果mid的阶乘的0数小于kl = mid + 1; //我们让l变为mid+1(大于mid,所以可以+1)//并且这里想让while循环中止就要不得不+1}}//二分法 l是最后的答案 if (calc(r) != k) {System.out.println(-1);} else {System.out.println(r);}}public static void main(String[] args) throws Exception{//System.out.println((Long.MAX_VALUE + 1)/2);// 大于Long.MAX_VALUE 会变成负数 所以有必要改进solve();}
}
试题 F: 最大子矩阵
【问题描述】
小明有一个大小为 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 7
8 4 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
【评测用例规模与约定】
评测用例编号 N M
1, 2 1 ≤ N ≤ 10 1 ≤ M ≤ 10
3, 4 N = 1 M ≤ 100000
5 ∼ 12 1 ≤ N ≤ 10 M ≤ 10000
13 ∼ 20 1 ≤ N ≤ 80 1 ≤ M ≤ 80
对于所有评测用例，0 ≤ 矩阵元素值, limit ≤ 105
【题解思路】
给定一个n * m的矩阵，求解满足矩阵内最大值与最小值的差值不超过limit的最大面积的矩阵
一开始觉得是单调栈，但是考场时间不够了，没时间细想，于是就直接暴力做法如下
暴力枚举法，从大到小枚举出最大长于宽，然后枚举每一个左上角顶点，计算该矩阵是否符合要求，维护一个最大面积。但是个人随着测试样例范围变大感觉会超时，可以提前对矩阵元素进行预处理，以降低复杂度
package lanqiao;import java.util.Scanner;public class F_最大子矩阵 {static int[][] arr;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int N=scanner.nextInt();int M=scanner.nextInt();arr=new int[N][M];for(int i=0;i<N;i++) {for(int j=0;j<M;j++) {arr[i][j]=scanner.nextInt();}}int limit = scanner.nextInt();int max_are = Integer.MIN_VALUE;for(int i=N;i>0;i--) {for(int j=M;j>0;j--) { // i*j的矩阵for(int x=0;x<=N-i;x++) {for(int y=0;y<=M-j;y++) { //左上角坐标int max = find_max(i,j,x,y);int min = find_min(i,j,x,y);if((max-min)<=limit) {max_are = Math.max(max_are, i*j);}}}}}System.out.println(max_are);}private static int find_min(int i, int j, int x, int y) {// TODO //寻找最小值int res = Integer.MAX_VALUE;for(int n=x;n<x+i;n++) {for(int m=y;m<y+j;m++) {res = Math.min(res, arr[n][m]);}}return res;}private static int find_max(int i, int j, int x, int y) {// TODO 寻找最大值int res = Integer.MIN_VALUE;for(int n=x;n<x+i;n++) {for(int m=y;m<y+j;m++) {res = Math.max(res, arr[n][m]);}}return res;}}试题 G: 数组切分
【问题描述】
已知一个长度为 N 的数组：A1, A2, A3, …AN 恰好是 1 ∼ N 的一个排列。现
在要求你将 A 数组切分成若干个 (最少一个，最多 N 个) 连续的子数组，并且
每个子数组中包含的整数恰好可以组成一段连续的自然数。
例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法：
{1}{3}{2}{4}：每个单独的数显然是 (长度为 1 的) 一段连续的自然数。 {1}{3, 2}{4}：{3, 2} 包含 2 到 3，是 一段连续的自然数，另外 {1} 和 {4} 显然
也是。
{1}{3, 2, 4}：{3, 2, 4} 包含 2 到 4，是 一段连续的自然数，另外 {1} 显然也是。
{1, 3, 2}{4}：{1, 3, 2} 包含 1 到 3，是 一段连续的自然数，另外 {4} 显然也是。
{1, 3, 2, 4}：只有一个子数组，包含 1 到 4，是 一段连续的自然数。
【输入格式】
第一行包含一个整数 N。第二行包含 N 个整数，代表 A 数组。
【输出格式】
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取
模后的值
【样例输入】
4
1 3 2 4
【样例输出】
5
【评测用例规模与约定】
对于 30% 评测用例，1 ≤ N ≤ 20.
对于 100% 评测用例，1 ≤ N ≤ 10000
【题解思路】
线性dp
如何判断一段区间是连续的一段自然数
假设是连续的，将这段区间排序，然后有：
最大值 - 最小值 + 1 = 区间长度 = 右端 - 左端 + 1
我们设立状态dp[i]表示[i, n - 1]这一段区间内数满足题意条件的划分方案的数量，其中i in [0, n - 1]。
特别的有，边界条件dp[n] = 1，即对于空的序列，只有一种划分方案（不划分）
当我们已知dp[head, tail]这一段区间的数连续时，若我们知道以[tail + 1, n - 1]这一段区间内的数的划分方案，显然，我们可以将其贡献dp[tail + 1]累加到dp[head]中
这样我们确定了状态求解的顺序为逆推了，对于每个head枚举所有比它大的tail，因为n = 1e4，故算法复杂度最终为，即大概刚好1e8，能ac
import java.util.Scanner;
public class Main{static int md = (int) (1e9 + 7);final static int N = (int) (1e4 + 4);static int a[] = new int[N];static long dp[] = new long[N];//i in [0, n - 1], dp[i]表示[i, n - 1]这一段区间内满足题意条件的划分方案的数量public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}dp[n] = 1;for (int head = n - 1; head >= 0; head --) {int mx = a[head];int mi = a[head];for (int tail = head; tail < n; tail++) {int len = tail - head + 1;//长度 = 右端 - 左端 + 1if(mx - mi + 1 == len){//[head, tail]这一段连续dp[head] = (dp[head] + dp[tail + 1]) % md;// 则可以加上dp[tail + 1]的贡献}mx = Math.max(mx, a[tail + 1]);mi = Math.min(mi, a[tail + 1]);}}System.out.print(dp[0]);}
}
另附上深搜算法遍历代码，同大家学习借鉴
/*** */
package lanqiao;import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class G_数组切分 {static boolean[] vis;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int[] arr = new int[N];vis = new boolean[N];for (int i = 0; i < N; i++) {arr[i] = scanner.nextInt();}long ans = DFS(arr, 0);System.out.println(ans);}private static long DFS(int[] arr, int k) {if (k == arr.length-1) {if (check(arr)) {
// for(int i=0;i<vis.length;i++) {
// System.out.print(vis[i] + " ");
// }
// System.out.println();return 1;}return 0;}// 当前位置切int res = 0;vis[k] = true;res += DFS(arr, k + 1);// 当前位置不切vis[k] = false;res += DFS(arr, k + 1);return res;}private static boolean check(int[] arr) {// TODO 检查当前切法是否符合规则int len = arr.length;int p = 0;int q = 1;while (q < len) {if (vis[q - 1]) {if (!check_lianxu(arr, p, q)) {return false;}p=q;}q++;}if(!check_lianxu(arr, p, q)) {return false;}return true;}private static boolean check_lianxu(int[] arr, int p, int q) {// TODO 检测数组是否连续p-qint[] arrcopy = new int[q-p];System.arraycopy(arr, p, arrcopy, 0, q-p);Arrays.sort(arrcopy);for(int i=0;i<q-p-1;i++) {if(arrcopy[i+1]-arrcopy[i]!=1) {return false;}}return true;}}
持续更新…🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇
欢迎添加微信，加入我的核心小队，请备注来意
👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇
