蓝桥杯大赛介绍
蓝桥杯全国软件和信息技术专业人才大赛是全国性的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; } }
