第十一届蓝桥杯第二次模拟赛

12.5MB

【问题描述】
在计算机存储中，12.5MB是多少字节？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

第一题没什么难度就是计算，1MB=1024KB，1KB=1024Byte，所以直接计算器，答案为13,107,200

最多边数

【问题描述】
一个包含有2019个结点的有向图，最多包含多少条边？（不允许有重边）
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

边数最多，那就是有向完全图了，所以根据数据结构的知识，含有n个节点的有向完全图，边数为n*(n-1)。所以答案为4074342。

单词重排

【问题描述】
将LANQIAO中的字母重新排列，可以得到不同的单词，如LANQIAO、AAILNOQ等，注意这7个字母都要被用上，单词不一定有具体的英文意义。
请问，总共能排列如多少个不同的单词。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

这明显就是全排序的题目，所以用全排序的算法就可以得出结果。

解法一

我一开始看到这填空题才是七个数的全排列，就直接笔算了，全排列后的种数为7！。因为题目里的这七个字母有两个是一样的，所以全排列后除2就可以得到答案2520。

解法二

第二种是在网上看到的灵感，就是先实现全排列，然后加入到set集合里去重，最后也可以得到正确答案。

import java.util.HashSet;
import java.util.Set;

public class Solution {
    static char[] arr = "LANQIAO".toCharArray();
    static Set<String> res = new HashSet<>();
	//start表示开始的位置，end表示最后的位置
    public static void Permutation(char[] arr,int start,int end){
        if (end <= 1) {
            return;
        }
        if (start == end) {
            res.add(new String(arr));
        }
        else{
            for (int i = 0; i <= end; i++) {
                swapchar(arr,i,start);
                Permutation(arr,start+1,end);
                swapchar(arr,i,start);
            }
        }

    }
    public static void swapchar(char[] arr,int a,int b){
        char t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }

    public static void main(String[] args) {
        Permutation(arr, 0, 6);
        System.out.println(res.size());
    }
}

括号序列

【问题描述】
由1对括号，可以组成一种合法括号序列：()。
由2对括号，可以组成两种合法括号序列：()()、(())。
由4对括号组成的合法括号序列一共有多少种？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解法一

这道题我一开始看的想法就是左括号和右括号看成0和1，然后直接枚举暴力破解，因为第一个肯定是左括号，最后一个肯定是右括号，所以输出了64种，一种种排除几分钟也能得到正确答案14种。

这种方法比较蠢，上了几个for循环，我就不放代码了。

解法二

在网上找到的一种方法。这其实是卡特兰数的一种应用（可以去百度了解一下） 。

S(n) = S(0)S(n-1) + S(1)S(n-2) + ….. + S(n-1)S(0)

所以就可以直接套公式了。

• 当有0对括号的时候，有1种序列
• 当有1对括号的时候，有1种序列
• 当有2对括号的时候，有2种序列
• 当有3对括号的时候，有5种序列

所以代进去就能得到答案为14，代码如下。

public class Solution {

    public static void main(String[] args) {
        System.out.println(Catalan(4));
    }

    public static int Catalan(int k){
        if(k<=1){
            return 1;
        }
        int[] res = new int[k+1];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i <= k; i++) {
            for (int j = 0; j < i; j++) {
                res[i] = res[i] + (res[j] * res[i - j - 1]);
            }
        }
        return res[k];
    }
}

反倍数

【问题描述】
给定三个整数 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。

这题也没什么技巧，最大的数据也只有1000000，所以一个for循环加个if判断语句就可以暴力破解了。

public class Solution {
    public static void main(String[] args) {
        int res = 0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            if(i%a!=0&&i%b!=0&&i%c!=0) {
                res++;
            }
        }
        System.out.println(res);
    }
}

凯撒加密

【问题描述】
给定一个单词，请使用凯撒密码将这个单词加密。
凯撒密码是一种替换加密的技术，单词中的所有字母都在字母表上向后偏移3位后被替换成密文。即a变为d，b变为e，...，w变为z，x变为a，y变为b，z变为c。
例如，lanqiao会变成odqtldr。
【输入格式】
输入一行，包含一个单词，单词中只包含小写英文字母。
【输出格式】
输出一行，表示加密后的密文。
【样例输入】
lanqiao
【样例输出】
odqtldr
【评测用例规模与约定】
对于所有评测用例，单词中的字母个数不超过100。

凯撒密码从c敲到Java，常见的题，我不是太清楚这个单词的结构，我默认它是一长串连续的字母组成的字符串，没有空格。

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        char[] arr = str.toCharArray();
        for(char c:arr) {
            if (c == 'x') {
                System.out.print('a');
            }
            if (c == 'y') {
                System.out.println('b');
            }
            if (c == 'z') {
                System.out.println('c');
            }
            System.out.print((char) (c + 3));
        }
    }
}

螺旋

【问题描述】
对于一个 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。

这个题目难点就是求出这个数组，我们可以螺旋递增来求出这个数组，然后再输出r行c列的值就好了。

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = 1,x=0,y = 0;
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int r = scanner.nextInt();
        int c = scanner.nextInt();
        int[][] arr = new int[n][m];
        arr[0][0] = k;
        while(n*m>k){
            //向右循环递增
            while (y + 1 < m && arr[x][y + 1]==0) {
                arr[x][y+1] = ++k;
                y++;
            }
            //向下循环递增
            while (x + 1 < n && arr[x+1][y]==0) {
                arr[x+1][y] = ++k;
                x++;
            }
            //向左循环递增
            while (y-1 >= 0 && arr[x][y-1]==0) {
                arr[x][y-1] = ++k;
                y--;
            }
            //向上循环递增
            while (x-1 >= 0 && arr[x-1][y]==0) {
                arr[x-1][y] = ++k;
                x--;
            }
        }
            System.out.println(arr[r-1][c-1]);
    }
}

摆动序列

通电

植树