第十二届蓝桥杯大赛模拟赛（第三期）题目与解答

---

第1题

问题描述

　　ASCII 码将每个字符对应到一个数值（编码），用于信息的表示和传输。在 ASCII 码中，英文字母是按从小到大的顺序依次编码的，例如：字母 A 编码是 65, 字母 B 编码是 66，字母 C 编码是 67，请问字母 Q 编码是多少？

答案提交

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

思路

ASCII码与整型互转

答案：

81

第2题

问题描述

　　请问在 1 到 2020 中，有多少个数与 2020 互质，即有多少个数与 2020 的最大公约数为 1。

答案提交

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

思路

public class Main2 {
    private static int gcd(int a, int b) {
        while (a != 0) {
            int t = a;
            a = b % a;
            b = t;
        }
        return b;
    }

    public static void main(String[] args) {
        int count = 0;
        for (int i = 1; i <= 2020; i++) {
            if (gcd(i, 2020) == 1) {
                ++count;
            }
        }
        System.out.println(count);
    }
}

答案：

800

第3题

问题描述

　　有一棵二叉树，一个由2021个结点，其中有1000个结点有两个子结点，其他的结点有一个或者0个子结点。
　　请问，这棵二叉树有多少个叶结点？

答案提交

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

思路

已知：node = 2021，node_2 = 1000， 求node_0 = ? (注：node_1表示只有一个子节点的节点)
node = 2021 ==> edge = node - 1 = 2020; (除root节点外，所有节点都有一条指向父节点的边)
node_2 = 1000 ==> edge_2 = node_2 * 2 = 2000;
node_1 = edge_1 = edge - edge_2 = 2020 - 2000 = 20;
node_0 = node - node_2 - node_1 = 2021 - 1000 - 20 = 1001;

答案：

1001

第4题

问题描述

　　对于整数 v 和 p，定义 Pierce 序列为：
　　a[1] = v
　　a[i] = p % a[i-1]
　　例如，当 v = 8, p = 21 时，对应的 Pierce 序列为
　　a[1] = 8
　　a[2] = 5
　　a[3] = 1
　　再往后计算，值变为 0，不在我们考虑的范围内。因此当 v = 8, p = 21 时， Pierce 序列的长度为 3。
　　当 p 一定时，对于不同的 v 值，Pierce 序列的长度可能不同。当 p = 8 时，若 1<=v<p，最长的 Pierce 序列出现在 v=13时，为(13, 8, 5, 1)，长度为 4。
　　当 p=2021 时，最长的 Pierce 序列出现在 v=1160 时，请问这个序列有多长？

答案提交

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

思路

//  Fibonacci数列的变种，题目中的第二个例子有问题，无视即可
public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int p = sc.nextInt();
        int v = sc.nextInt();
        int count = 1; // for a[1]
        int last = v; // last is a[i-1]

        // System.out.println(last);
        while (last != 1 && last != 0) {
            last = p % last;
            if (last == 0) {
                break;
            }
            // System.out.println(last);
            count++;
        }
        System.out.println(count);
    }

答案：

12

第5题

问题描述

　　在 Excel 中，第 1 列到第 26 列的列名依次为 A 到 Z，从第 27 列开始，列名有两个字母组成，第 27 列到第 702 列的列名依次为 AA 到 ZZ。
　　之后的列再用 3 个字母、4 个字母表示。
　　请问，第 2021 列的列名是什么？

答案提交

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个有大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

思路

// 进制转换（十进制转为26进制）
// Integer封装了进制转换的方法 Integer.toString(i, radix)
// 但表示方法是 0123456789 abcdefghijklmnopqrstuvwxyz，可以通过该方法求1-36范围的进制转换
public static void main(String[] args) {
    char[] chars = Integer.toString(2021, 26).toCharArray();
    for (char c : chars) {
        char cc;
        if (c <= '9') {
            cc = (char) (c - '0' - 1 + 'A');
        } else {
            cc = (char) (c - 'a' - 1 + 'A' + 10);
        }
        System.out.print(cc);
    }
    System.out.println();
}

答案：

BYS

第6题

问题描述

　　在书写一个较大的整数时，为了方便看清数位，通常会在数位之间加上逗号来分割数位，具体的，从右向左，每三位分成一段，相邻的段之间加一个逗号。
　　例如，1234567 写成 1,234,567。
　　例如，17179869184 写成 17,179,869,184。
　　给定一个整数，请将这个整数增加分割符后输出。

输入格式

　　输入一行包含一个整数 v。

输出格式

　　输出增加分割符后的整数。

样例输入

1234567

样例输出

1,234,567

样例输入

17179869184

样例输出

17,179,869,184

数据规模和约定

　　对于 50% 的评测用例，0 <= v < 10^9 (10的9次方)。
　　对于所有评测用例，0 <= v < 10^18 (10的18次方)。

答案：

public static void main(String[] args) {
    StringBuilder sb = new StringBuilder();
    java.util.Scanner sc = new java.util.Scanner(System.in);
    String s = sc.next();
    for (int i = 0; i < s.length(); i++) {
        sb.append(s.charAt(s.length() - i - 1));
        if ((i + 1) % 3 == 0 && (i + 1) < s.length()) {
            sb.append(',');
        }
    }
    System.out.println(sb.reverse().toString());
}

第7题

问题描述

　　小蓝正在写一个网页显示一个新闻列表，他需要将总共 n 条新闻显示，每页最多可以显示 p 条，请问小蓝至少需要分多少页显示？
　　例如，如果要显示2021条新闻，每页最多显示10条，则至少要分203页显示。

输入格式

　　输入的第一行包含一个整数 n，表示要显示的新闻条数。
　　第二行包含一个整数 p，表示每页最多可以显示的条数。

输出格式

　　输出一个整数，表示答案。

样例输入

2021
10

样例输出

203

样例输入

2020
20

样例输出

101

数据规模和约定

　　对于所有评测用例，1 <= n <= 10000，1 <= p <= 100。

答案：

public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    int p = sc.nextInt();
    int x = n / p + (n % p == 0 ? 0 : 1);
    System.out.println(x);
}

第8题

问题描述

　　杂货铺老板一共有N件物品，每件物品具有ABC三种属性中的一种或多种。从杂货铺老板处购得一件物品需要支付相应的代价。
　　现在你需要计算出如何购买物品，可以使得ABC三种属性中的每一种都在至少一件购买的物品中出现，并且支付的总代价最小。

输入格式

　　输入第一行包含一个整数N。
　　以下N行，每行包含一个整数C和一个只包含”ABC”的字符串，代表购得该物品的代价和其具有的属性。

输出格式

　　输出一个整数，代表最小的代价。如果无论如何凑不齐ABC三种属性，输出-1。

样例输入

5
10 A
9 BC
11 CA
4 A
5 B

样例输出

13

数据规模和约定

　　对于50%的评测用例，1 <= N <= 20
　　对于所有评测用例，1 <= N <= 1000， 1 <= C <= 100000

思路

构造一个hash表，分别存放A、B、C、AB、AC、BC、ABC对应的最低代价，最后遍历A+B+C、AB+C、AC+b、BC+A、ABC这四种情况找出最小代价即可。

答案：

public static void main(String[] args) {
    int MAX_INT = 100000 + 10;
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int[] weight = new int[10];
    for (int i = 0; i < 10; i++) {
        weight[i] = MAX_INT;
    }
    int n = sc.nextInt();
    int p;
    String s;
    for (int i = 0; i < n; i++) {
        p = sc.nextInt();
        s = sc.next();
        // System.out.println(p + "--" + s);
        if (weight[getIndex(s)] > p) {
            weight[getIndex(s)] = p;
        }
    }
    int result = MAX_INT;
    result = Math.min(result, weight[getIndex("ABC")]);
    result = Math.min(result, (weight[getIndex("AB")] + weight[getIndex("C")]));
    result = Math.min(result, (weight[getIndex("BC")] + weight[getIndex("A")]));
    result = Math.min(result, (weight[getIndex("AC")] + weight[getIndex("B")]));
    result = Math.min(result, (weight[getIndex("A")] + weight[getIndex("B")] + weight[getIndex("C")]));
    System.out.println(result);
}
private static int getIndex(String s) {
    // A = 1, B = 2, C = 4
    // AB = 3, AC = 5, BC = 6
    // ABC = 7
    if (s == null || s.length() == 0) {
        return 0;
    }
    int containA = 0, containB = 0, containC = 0;
    if (s.contains("A")) {
        containA = 1;
    }
    if (s.contains("B")) {
        containB = 2;
    }
    if (s.contains("C")) {
        containC = 4;
    }
    return (containA + containB + containC);
}

第9题

问题描述

　　给定一个矩阵 M，由 n 行 m 列组成，第 i 行第 j 列值为 M[i][j]。
　　定义矩阵 M 的重量为矩阵中所有元素的和，几位weight(M)
　　请找到矩阵左上角的一个子矩阵S（矩阵的前 r 行中的前 c 列组成），使得这个子矩阵的重量的两倍最接近矩阵 M 重量。即 |2 weight(S)-weight(M)| 最小。
　　如果有多个子矩阵满足条件，请找出面积 r * c 最小的一个。
　　如果仍然有多个子矩阵满足条件，请找出其中 r 最小的一个。

输入格式

　　输入第一行包含两个整数 n, m，表示矩阵的大小。
　　接下来 n 行，每行 m 个整数，表示给定的矩阵M。

输出格式

　　输出一行，包含两个整数 r, c，表示子矩阵为矩阵 M 的前 r 行中的前 c 列。

样例输入

3 4
3 0 1 1
1 0 1 1
1 1 -2 4

样例输出

2 3

数据规模和约定

　　对于 30% 的评测用例，1 <= n, m <= 20, -10 <= M[i][j] <= 10。
　　对于 50% 的评测用例，1 <= n, m <= 100, -100 <= M[i][j] <= 100。
　　对于所有评测用例，1 <= n, m <= 1000, -1000 <= M[i][j] <= 1000。

思路

先求出i行j列的重量并保存在weight[i][j]数组中，然后遍历该数组找出符合要求的 r、c

答案：

public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int[][] M = new int[1001][1001];
    int[][] weight = new int[1001][1001];
    int n, m;
    n = sc.nextInt();
    m = sc.nextInt();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            M[i][j] = sc.nextInt();
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int jWeight = 0;
            for (int k = 1; k <= i; k++) {
                jWeight += M[k][j];
            }
            weight[i][j] = weight[i][j - 1] + jWeight;
            // System.out.println(weight[i][j] + "---" + jWeight);
        }
    }
    int r = 0, c = 0, flag = Integer.MAX_VALUE;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int temp = Math.abs(2 * weight[i][j] - weight[n][m]);
            if (temp < flag) {
                flag = temp;
                r = i;
                c = j;
            } else if (temp == flag && (i * j) < (r * c)) {
                r = i;
                c = j;
            } else if (temp == flag && (i * j) == (r * c) && (i < r)) {
                r = i;
                c = j;
            }
        }
    }
    System.out.println(r + " " + c);
}

第10题

问题描述

　　给定一个序列 (a_1, a_2, …, a_n), 它的一个上升子序列是指从序列中取出一些元素，按照原来的顺序排列后，是单调递增的序列。
　　例如，对于序列 (3, 2, 7, 6, 7)，取出下标为 2, 4, 5 的元素 a_2, a_4, a_5，即 2, 6, 7，是一个上升子序列。
　　在这个序列中，有 7 个长度为 2 的上升子序列，例如

    1. 下标 1, 3 对应的 3, 7；
    2. 下标 1, 4 对应的 3, 6；
    3. 下标 1, 5 对应的 3, 7；
    4. 下标 2, 3 对应的 2, 7；
    5. 下标 2, 4 对应的 2, 6；
    6. 下标 2, 5 对应的 2, 7；
    7. 下标 4, 5 对应的 6, 7。

　　注意，可能有下标不同但对应数值相同的上升子序列，他们应当算成不同的上升子序列。
　　给定序列，请问序列中一共有多少个长度为 k 的上升子序列。

输入格式

　　输入第一行包含两个整数 n, k，表示序列的长度和上升子序列的长度。
　　第二行包含 n 个整数 a_1, a_2, …, a_n，表示给定的序列。

输出格式

　　输出一行，包含一个整数，表示长度为 k 的上升子序列的数量，答案可能很大，请输出答案除以 1000007 的余数。

样例输入

5 2
3 2 7 6 7

样例输出

7

数据规模和约定

　　对于 30% 的评测用例，1 <= n <= 20, 0 <= a_i <= 100。
　　对于 50% 的评测用例，1 <= n <= 100, 0 <= a_i <= 1000。
　　对于所有评测用例，1 <= n <= 1000, 1 <= k <= 10, 0 <= a_i <= 10000。

答案（暴力递归）：

static int count = 0;
public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int[] array = new int[1000 + 5];
    int n = sc.nextInt();
    int k = sc.nextInt();
    for (int i = 0; i < n; i++) {
        array[i] = sc.nextInt();
    }
    f(array, 0, Integer.MIN_VALUE, 1, k);
    System.out.println(count % 1000007);
}
public static int f(int[] array, int start, int aim, int kth, int len) {
    if (kth > len) {
        count++;
        // System.out.println("finded!");
        return 1;
    }
    for (int i = start; i < array.length - (len - kth); i++) {
        if (array[i] > aim) {
            f(array, i + 1, array[i], kth + 1, len);
        }
    }
    return 0;
}

思路（动态规划）

dp[i][j]表示以array[i]结尾，长度为j的上升子序列的数量，状态转移方程如下：
	dp[i][1] = 1
	dp[i][j] = sum(dp[i][j - 1]), (0 <= t < i && array[t] < array[i])

输出结果为： sum(dp[i][k]), (0 <= i < n)

答案（动态规划）：

public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int mod = 1000007;
    int[] array = new int[1000 + 5];
    int n = sc.nextInt();
    int k = sc.nextInt();
    for (int i = 0; i < n; i++) {
        array[i] = sc.nextInt();
    }
    int[][] dp = new int[n][k + 1];
    for (int i = 0; i < n; i++) {
        dp[i][1] = 1;
    }
    for (int j = 2; j <= k; j++) {
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int t = 0; t < i; t++) {
                if (array[t] < array[i]) {
                    sum += dp[t][j - 1];
                }
            }
            dp[i][j] = sum;
        }
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        count += dp[i][k];
    }
    System.out.println(count);
}

---

likeqc
ends