个人名片：
🐼作者简介：一名大二在校生，喜欢编程🎋
🐻❄️个人主页🥇：小新爱学习.
🐼个人WeChat：hmmwx53
🕊️系列专栏：🖼️🐓每日一句：🍭我很忙，但我要忙的有意义！
文章目录
第十四届蓝桥杯全国软件和信息技术专业人才大赛
蓝桥杯大赛介绍
蓝桥杯全国软件和信息技术专业人才大赛是全国性的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的阶乘后边有多少个0
static 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;//方便学习可以debug
while (l < r) {
long mid = (l + r) / 2;
if (k <= calc(mid)) {//如果mid的阶乘的0数大于等于k
r = mid;//我们让r变为mid (可以等于mid)
} else {//如果mid的阶乘的0数小于k
l = 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;
//长度 = 右端 - 左端 + 1
if(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-q
int[] 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;
}
}
持续更新…🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇🥇
欢迎添加微信，加入我的核心小队，请备注来意
👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇