第十一届蓝桥杯大赛第二次模拟（软件类）真题

以下为第十一届蓝桥杯大赛第二次模拟（软件类）真题加我写的题解，如有错误望指正。

题一

【问题描述】 在计算机存储中，12.5MB是多少字节？ 【答案提交】 12.5 * 1024 * 1024

题二

【问题描述】 一个包含有2019个结点的有向图，最多包含多少条边？（不允许有重边） 【答案提交】 2019 * 2018

题三

【问题描述】   将LANQIAO中的字母重新排列，可以得到不同的单词，如LANQIAO、AAILNOQ等，注意这7个字母都要被用上，单词不一定有具体的英文意义。   请问，总共能排列如多少个不同的单词。 【答案提交】   数学方法就是7！/ 2（俩个A）   也可以写出所有的字符排列顺序，加入到set中统计个数

题四

【问题描述】 由1对括号，可以组成一种合法括号序列：()。 由2对括号，可以组成两种合法括号序列：()()、(())。 由4对括号组成的合法括号序列一共有多少种？ 【答案提交】   直接套卡特兰数的公式了，n个右括号前一定要有n个左括号。

题五

【问题描述】 给定三个整数 a, b, c，如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。 请问在 1 至 n 中有多少个反倍数。 【输入格式】 输入的第一行包含一个整数 n。 第二行包含三个整数 a, b, c，相邻两个数之间用一个空格分隔。 【输出格式】 输出一行包含一个整数，表示答案。 【样例输入】 30 2 3 6 【样例输出】 10 【样例说明】 以下这些数满足要求：1, 5, 7, 11, 13, 17, 19, 23, 25, 29。 【评测用例规模与约定】 对于 40% 的评测用例，1 <= n <= 10000。 对于 80% 的评测用例，1 <= n <= 100000。 对于所有评测用例，1 <= n <= 1000000，1 <= a <= n，1 <= b <= n，1 <= c <= n。

直接暴力

题六

【问题描述】   给定一个单词，请使用凯撒密码将这个单词加密。凯撒密码是一种替换加密的技术，单词中的所有字母都在字母表上向后偏移3位后被替换成密文。即a变为d，b变为e，...，w变为z，x变为a，y变为b，z变为c。   例如，lanqiao会变成odqtldr。 【输入格式】   输入一行，包含一个单词，单词中只包含小写英文字母。 【输出格式】   输出一行，表示加密后的密文。 【样例输入】 lanqiao 【样例输出】 odqtldr 【评测用例规模与约定】 对于所有评测用例，单词中的字母个数不超过100。 class Main { public static void main(String[] args) { String str = "lanqiao"; char[] arr = str.toCharArray(); for (int i = 0; i < arr.length; i++) { arr[i] = (char) ((arr[i] + 3 - 97) % 26 + 'a'); } StringBuffer buffer = new StringBuffer(); for (char c : arr) { buffer.append(c); } System.out.println(buffer.toString()); } } 【问题描述】   对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。   例如，一个 4 行 5 列的螺旋矩阵如下： 1 2 3 4 5 14 15 16 17 6 13 20 19 18 7 12 11 10 9 8 【输入格式】   输入的第一行包含两个整数 n, m，分别表示螺旋矩阵的行数和列数。   第二行包含两个整数 r, c，表示要求的行号和列号。 【输出格式】   输出一个整数，表示螺旋矩阵中第 r 行第 c 列的元素的值。 【样例输入】 4 5 2 2 【样例输出】 15 【评测用例规模与约定】 对于 30% 的评测用例，2 <= n, m <= 20。 对于 70% 的评测用例，2 <= n, m <= 100。 对于所有评测用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m。

注意输出的行号列好是从1开始的…

public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); scanner.nextLine(); int x = scanner.nextInt(); int y = scanner.nextInt(); int[][] arr = new int[n][m]; insert(arr); System.out.println(arr[x-1][y-1]); } private static void insert(int[][] arr){ int l = 0; int r = arr[0].length - 1; int u = 0; int d = arr.length - 1; int num = 1; int dir = 0; while(num < arr.length * arr[0].length){ if(dir == 0){ //往右 for(int i = l; i <= r; i++, num++){ arr[u][i] = num; } u++; } if(dir == 1){ //往下 for(int i = u; i <= d; i++, num++){ arr[i][r] = num; } r--; } if(dir == 2){ //往zuo for(int i = r; i >= l; i--, num++){ arr[d][i] = num; } d--; } if(dir == 3){ //往shang for(int i = d; i >= u; i--, num++){ arr[i][l] = num; } l++; } dir= (dir + 1) % 4; } }

题7

【问题描述】 如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。 小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。 【输入格式】 输入一行包含两个整数 m，n。 【输出格式】 输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。 【样例输入】 3 4 【样例输出】 14 【样例说明】 以下是符合要求的摆动序列： 2 1 2 2 1 3 2 1 4 3 1 2 3 1 3 3 1 4 3 2 3 3 2 4 4 1 2 4 1 3 4 1 4 4 2 3 4 2 4 4 3 4 【评测用例规模与约定】 对于 20% 的评测用例，1 <= n, m <= 5； 对于 50% 的评测用例，1 <= n, m <= 10； 对于 80% 的评测用例，1 <= n, m <= 100； 对于所有评测用例，1 <= n, m <= 1000。

第一种暴力，但我想应该会超时O(n^m)

class Main { static int n; static int m; static int count; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); m = scanner.nextInt(); n = scanner.nextInt(); ArrayList<List<Integer>> objects = new ArrayList<>(); objects.add(new ArrayList<>()); bfs(m, objects); System.out.println(count); } private static void bfs(int index, List<List<Integer>> list){ if(index != 0){ int size = list.size(); for(int j = 0; j < size; j++){ List sublist = list.get(j); for(int i = 1; i <= n; i++){ List<Integer> k = new ArrayList<>(sublist); k.add(i); list.add(k); } } bfs(index- 1,list); }else{ for (List<Integer> sublist : list) { if(is(sublist)){ System.out.println(sublist.toString()); count++; } } } } private static boolean is(List<Integer> list){ if(list.size() != m){ return false; } for (int i = 1; i < list.size(); i++) { if(i %2 ==1 && list.get(i) <= list.get(i-1)){ return false; } if(i % 2 == 0 && list.get(i) >= list.get(i -1)){ return false; } } return true; } }

你按照我说的状态画一张表瞬间就能明白! 动态规划解法 状态dp[i][j]表示序列长度为i，并且末尾数是j时，符号条件的总个数。 转移方程：

如果i是偶数，也就是最后一项是偶数项，那么要看i-1列。 dp[i][j]结果就是前一列中最后一项大于j的和，因为偶数项要大于前一项的。 dp[i][j] = dp[i+1][j-1]+ dp[i+2][j-1] +… dp[n][j-1];同理，如果i是奇数，最后一项为奇数，那么 dp[i][j] = dp[1][j-1]+dp[2][j-1]+…dp[i-1][j-1]; class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int m = scanner.nextInt(); int n = scanner.nextInt(); //dp[i][j]表示序列为i项，并且最后一项是j，这样的序列总数 //最后的结果就是dp[1-n][m],也就是最后一列的和， // 最后一列的和意思就是：i项序列，i项序列最后一个数分别是1-n，这就包括了所有的分类情况了 //所以最后的结果是最后一列的和 int[][] dp = new int[n + 1][m + 1]; //边界问题好处理多一列和一行 for(int i = 1; i <= n; i++){ //初始化第一列为1，因为序列项数为1时，那么不管最后数为几，满足条件的只有一个 dp[i][1] = 1; } for(int j = 2; j <= m; j++){ //j是第几项 for(int i = 1; i <= n; i++){ if(j % 2 == 0){ int num = 0; for(int k = i+1; k <= n; k++){ num += dp[k][j-1]; } dp[i][j] = num; }else{ int num = 0; for(int k = i - 1; k > 0; k--){ num += dp[k][j-1]; } dp[i][j] = num; } } } int count = 0; for(int j = 1; j <= n; j++){ count += dp[j][m]; } System.out.println(count); } }