蓝桥杯 2023 训练二 Java 全解

注意

该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。

为了节省篇幅，在不影响阅读的前提下，代码中将省略import语句；同时，也不再给出输入和输出样例；过于简单的题也不再文字说明解题思路。

自动编程

输出语句是每个程序员首先要掌握的语句。Python 的输出语句很简单，只要写一个print(X)即可，其中X是需要输出的内容。

本题就请你写一个自动编程机，对任何一个要输出的整数 N，给出输出这个整数的 Python 语句。

输入格式

输入给出一个不超过 10⁵的正整数。

输出格式

在一行中打印输出这个整数的 Python 语句，其中不包含任何空格。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.printf("print(%d)", scanner.nextInt());
    }

}

种钻石

2019年10月29日，中央电视台专题报道，中国科学院在培育钻石领域，取得科技突破。科学家们用金刚石的籽晶片作为种子，利用甲烷气体在能量作用下形成碳的等离子体，慢慢地沉积到钻石种子上，一周“种”出了一颗 1 克拉大小的钻石。

本题给出钻石的需求量和人工培育钻石的速度，请你计算出货需要的时间。

输入格式

输入在一行中给出钻石的需求量 N（不超过 10⁷的正整数，以微克拉为单位）和人工培育钻石的速度 v（1 ≤ v ≤ 200，以微克拉/天为单位的整数）。

输出格式

在一行中输出培育 N 微克拉钻石需要的整数天数。不到一天的时间不算在内。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();
        System.out.println(n / v);
    }

}

冠军魔术

2018 年 FISM（世界魔术大会）近景总冠军简纶廷的表演中有一个情节：以桌面上一根带子为界，当他将纸牌从带子的一边推到另一边时，纸牌会变成硬币；把硬币推回另一边会变成纸牌。

这里我们假设纸牌会变成等量的硬币，而硬币变成纸牌时，纸牌的数量会加倍。那么给定纸牌的初始数量，当他来回推了 N 次（来/回各算一次）后，手里拿的是纸牌还是硬币？数量是多少？

输入格式

输入在一行里给出两个正整数，分别是纸牌的初始数量和魔术师推送的次数。这里假设初始状态下魔术师手里全是纸牌。

输出格式

如果最后魔术师手里是纸牌，输出 0 和纸牌数量；如果是硬币，则输出 1 和硬币数量。数字间须有 1 个空格。题目保证结果数值不超出整型范围（即 2³¹− 1）。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 纸牌初始数量
        int c = scanner.nextInt();  // 推的次数
        System.out.printf("%d %d", c & 1, n << (c >> 1));
    }

}

组合数的和

给定 N 个非 0 的个位数字，用其中任意 2 个数字都可以组合成 1 个 2 位的数字。要求所有可能组合出来的 2 位数字的和。例如给定 2、5、8，则可以组合出：25、28、52、58、82、85，它们的和为330。

输入格式

输入在一行中先给出 N（1 < N < 10），随后一行给出 N 个不同的非 0 个位数字。数字间以空格分隔。

输出格式

输出所有可能组合出来的2位数字的和。

题解

注意一个数本身不能和它自身拼成两位数就可以了。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] input = new int[n];
        int ans = 0;
        for (int i = 0; i != n; ++i) input[i] = scanner.nextInt();
        for (int i = 0; i != n; ++i) {
            for (int k = 0; k != n; ++k) {
                if (i != k) ans += input[i] * 10 + input[k];
            }
        }
        System.out.println(ans);
    }

}

不变初心的数

不变初心数是指这样一种特别的数，它分别乘 2、3、4、5、6、7、8、9 时，所得乘积各位数之和却不变。例如 18 就是这样的数：18 的 2 倍是 36，3 + 6 = 9；18 的 3 倍是 54，5 + 4 = 9；…… 18 的 9 倍是 162，1 + 6 + 2 = 9。对于 18 而言，9 就是它的初心。本题要求你判断任一个给定的数是否有不变的初心。

输入格式

输入在第一行中给出一个正整数 N（≤ 100）。随后 N 行，每行给出一个不超过 10⁵的正整数。

输出格式

对每个给定的数字，如果它有不变的初心，就在一行中输出它的初心；否则输出NO。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i != n; ++i) {
            int input = scanner.nextInt();
            int[] res = IntStream.range(2, 10)  // 生成 [2, 9] 的 Stream
                    .map(it -> sum(it * input)) // 计算各个数的各个位的和
                    .distinct()                 // 去重
                    .toArray();                 // 将 Stream 转换为数组
            // 如果数组长度为 1 说明具有初心，否则没有
            if (res.length == 1) System.out.println(res[0]);
            else System.out.println("NO");
        }
    }

    /** 求一个数各个位上的和 */
    static int sum(int data) {
        int res = 0;
        while (data != 0) {
            res += data % 10;
            data /= 10;
        }
        return res;
    }

}

统计一行文本的单词个数

本题目要求编写程序统计一行字符中单词的个数。所谓“单词”是指连续不含空格的字符串，各单词之间用空格分隔，空格数可以是多个。

输入格式

输入给出一行字符。

输出格式

在一行中输出单词个数。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // nextLine() 后用 split 计数也可以，使用 split 时注意处理连续空格的情况
        int ans = 0;
        while (scanner.hasNext()) {
            ++ans;
            scanner.next();
        }
        System.out.println(ans);
    }

}

找鞍点

一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。

本题要求编写程序，求一个给定的 n 阶方阵的鞍点。

输入格式

输入第一行给出一个正整数 n（1 ≤ n ≤ 6）。随后n行，每行给出 n 个整数，其间以空格分隔。

输出格式

输出在一行中按照“行下标列下标”（下标从 0 开始）的格式输出鞍点的位置。如果鞍点不存在，则输出“NONE”。题目保证给出的矩阵至多存在一个鞍点。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] input = new int[n][n];
        for (int y = 0; y != n; ++y) {
            for (int x = 0; x != n; ++x) {
                input[y][x] = scanner.nextInt();
            }
        }
        for (int y = 0; y != n; ++y) {
            for (int x = 0; x != n; ++x) {
                if (check(input, n, x, y)) {
                    System.out.printf("%d %d", y, x);
                    return;
                }
            }
        }
        System.out.println("NONE");
    }

    /** 检查指定点是否是鞍点 */
    static boolean check(int[][] input, int n, int x, int y) {
        for (int i = 0; i != n; ++i) {
            if (
                input[i][x] < input[y][x] ||
                input[y][i] > input[y][x]
            ) return false;
        }
        return true;
    }

}

吉老师的回归

曾经在天梯赛大杀四方的吉老师决定回归天梯赛赛场啦！

为了简化题目，我们不妨假设天梯赛的每道题目可以用一个不超过 500 的、只包括可打印符号的字符串描述出来，如：Problem A: Print "Hello world!"。

众所周知，吉老师的竞赛水平非常高超，你可以认为他每道题目都会做（事实上也是……）。因此，吉老师会按照顺序看题并做题。但吉老师水平太高了，所以签到题他就懒得做了（浪费时间），具体来说，假如题目的字符串里有qiandao或者easy（区分大小写）的话，吉老师看完题目就会跳过这道题目不做。

现在给定这次天梯赛总共有几道题目以及吉老师已经做完了几道题目，请你告诉大家吉老师现在正在做哪个题，或者吉老师已经把所有他打算做的题目做完了。

提醒：天梯赛有分数升级的规则，如果不做签到题可能导致团队总分不足以升级，一般的选手请千万不要学习吉老师的酷炫行为！

输入格式

输入第一行是两个正整数 N，M (1 ≤ M ≤ N ≤ 30)，表示本次天梯赛有 N 道题目，吉老师现在做完了 M 道。

接下来 N 行，每行是一个符合题目描述的字符串，表示天梯赛的题目内容。吉老师会按照给出的顺序看题——第一行就是吉老师看的第一道题，第二行就是第二道，以此类推。

输出格式

在一行中输出吉老师当前正在做的题目对应的题面（即做完了 M 道题目后，吉老师正在做哪个题）。如果吉老师已经把所有他打算做的题目做完了，输出一行Wo AK le。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i != n; ++i) {
            String text = scanner.nextLine();
            if (text.contains("easy") || text.contains("qiandao")) continue;
            if (m-- == 0) {
                System.out.println(text);
                return;
            }
        }
        System.out.println("Wo AK le");
    }

}

房间

终于到了假期了，老师决定带领ACM队员们出去游山玩水，计划出行两天，这样的话中间就需要找个地方住宿一晚。

恰巧，老师带领队员们来到了这么一所酒店，这所酒店只有双人间（最多住两人）和三人间（最多住三人），但是价格不同，现在我们算上老师，一共有 n 个人，酒店的双人间价格是 a 元，三人间价格是 b 元，现在老师想知道怎样安排房间才能使得花销最小，你能帮助老师计算出最小的花销吗？

输入格式

第一行给出一个正整数 T（1 ≤ T ≤ 1000），代表测试数据的组数。

接下来 T 行每行给出三个正整数 n，a，b，1 ≤ n，a，b ≤ 10⁹，含义如题。

输出格式

输出包含 T 行，每行对应一组样例的输出。

题解

这道题总体思路就是列出几个可能的最省钱的情况，然后计算出来取最小值。

PTA 上这道题 Java 是过不了的。

import static java.lang.Math.min;

public class Main {

    public static void main(String[] args) throws IOException {
        int t = read();
        for (int i = 0; i != t; ++i) {
            int n = read();
            long a = read(), b = read();
            if (n < 3) {    // 排除掉 n = 1 | 2 的情况
                System.out.println(min(a, b));
                continue;
            }
            long[] ans = {
                    // 1：能住三人间的都住三人间，其他人住双人间（最多一个）
                    (n / 3) * b + min(n % 3, 1) * a,
                    // 2：能住双人间的都住双人间，其它住三人间（最多一个）
                    (n & 1) * b + (n >> 1) * a,
                    // 3：所有人都住三人间
                    ((n + 2) / 3) * b,
                    // 4：所有人都住双人间
                    ((n + 1) >> 1) * a,
                    // 5：在(2)的基础上，将一个双人间中的两个人分到三人间
                    b + ((n - 2) >> 1) * a,
                    // 6：在(1)的基础上，将三人间中的两个人分到双人间
                    ((n - 2) / 3) * b + (a << 1)
            };
            long res = Long.MAX_VALUE;
            for (long value : ans) {
                res = min(res, value);
            }
            System.out.println(res);
        }
    }

    /** 没有考虑负数的快读 */
    static int read() throws IOException {
        int x = 0;
        int ch = System.in.read();
        while (ch < '0' || ch > '9') {
            ch = System.in.read();
        }
        while (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = System.in.read();
        }
        return x;
    }

}

有趣的队列

本题重新定义队列出队的操作：队首出队的数字重新在队尾入队。

例：队列中有1 2 3三个数字，现要求队首出队，则1从队首出队，同时1从队尾入队，队列变成2 3 1。

入队的顺序为1, 2, 3, 4 … n，同时给一个二进制字符串，1 代表出队操作，0 代表入队操作。

输入格式

在第一行有两个数字n，m（n <= 100, n < m），其中 n 为入队的数字个数，m 代表操作数。

接下来 m 行，每行一个数字，1 或者 0，代表不同的操作。

输出格式

输出操作后队列的每个数字，数字间以空格分隔，最后一个数字后没有空格。

题解

直接模拟即可，PTA 上用 Java 过不了这道题。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Deque<Integer> deque = new ArrayDeque<>(n);
        for (int i = 0; i != m; ++i) {
            int op = scanner.nextInt();
            if (op == 0) deque.add(deque.size() + 1);
            else deque.add(deque.removeFirst());
        }
        System.out.println(deque.stream().map(String::valueOf)
                .collect(Collectors.joining(" ")));
    }

}

消掉 ACM

小李是程序设计竞赛爱好者，他现在遇到了这么一个问题：给定一个只有A，C，M三个字母组成的字符串且长度不超过 10000000。如果字符串中存在“ACM”子串，那么这个“ACM”子串可以自动消掉，消掉后，后面的元素都前移再变成一个新的完整的字符串。这个新串继续这样做，直到被消成空串或不再有”ACM”子串。GGS的任务是判断给定的字符串是否能被消为空串，如果可以，那么输出 YES,否则输出 NO。当然，小李可以很快完成这个简单的问题，你也快点去完成吧~

输入格式

输入一个字符串只含有A，C，M（大写）且非空。

输出格式

输出YES或NO，输出单独占一行。

题解

方法很简单，一个字符一个字符读入，然后没读入一个就往前判断能消掉多少个“ACM”，消不掉之后再继续读。

public class Main {

    public static void main(String[] args) throws IOException {
        int[] list = new int[10000000];
        int size = 0;
        while (true) {
            // 不使用 System.in.read 的话在 PTA 上是过不了的，会炸内存
            int value = System.in.read();
            if (value == -1 || value == 10) break;
            list[size++] = value - 'A';
            while (size > 2) {
                if (list[size - 3] == 0 && list[size - 2] == 2 && list[size - 1] == 12) {
                    size -= 3;
                } else break;
            }
        }
        System.out.println(size == 0 ? "YES" : "NO");
    }

}

最大子列和问题

给定 K 个整数组成的序列 { N₁, N₂, …, N_K}，“连续子列”被定义为{ N_i, N_i+1, …, N_j}，其中 1 ≤ i ≤ j ≤ K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列 { -2, 11, -4, 13, -5, -2 }，其连续子列 { 11, -4, 13 } 有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据 1：与样例等价，测试基本正确性；
数据 2：102 个随机整数；
数据 3：103 个随机整数；
数据 4：104 个随机整数；
数据 5：105 个随机整数。

输入格式

输入第1行给出正整数 K (≤ 100000)；第 2 行给出 K 个整数，其间以空格分隔。

输出格式

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出 0。

题解

前缀和问题，Java 不用快读在 PTA 上过不去。

public class Main {

    public static void main(String[] args) throws IOException {
        int n = read();
        int[] sum = new int[100001];
        for (int i = 1; i <= n; ++i) {
            int k = read();
            sum[i] = k + sum[i - 1];
        }
        int ans = 0;
        for (int i = 0; i != n; ++i) {
            for (int k = i + 1; k <= n; ++k) {
                ans = Math.max(ans, sum[k] - sum[i]);
            }
        }
        System.out.println(ans);
    }

    /** 考虑负数的快读 */
    static int read() throws IOException {
        int x = 0, t = 1;
        int ch = System.in.read();
        while (ch < '0' || ch > '9') {
            if (ch == '-') t = -1;
            ch = System.in.read();
        }
        while (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = System.in.read();
        }
        return x * t;
    }

}

数字三角形

观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。

金字塔

在上面的样例中，从 13 到 8 到 26 到 15 到 24 的路径产生了最大的和 86。

输入格式

第一个行包含 R（1 ≤ R ≤ 1000），表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

所有的被供应的整数是非负的且不大于 100。

输出格式

单独的一行，包含那个可能得到的最大的和。

题解

可以看作是一个最长路的问题，存储每个节点可能的最大值即可。由于直接在数组上进行修改会影响下一个节点的计算，所以需要两个数组替换使用。

public class Main {

    public static void main(String[] args) throws IOException {
        int r = read();
        int[] prev = new int[r + 2];
        int[] now = new int[r + 2];
        for (int i = 1; i <= r; ++i) {
            for (int k = 1; k <= i; ++k) {
                int value = read();
                now[k] = Math.max(prev[k - 1], prev[k]) + value;
            }
            int[] tmp = prev;
            prev = now;
            now = tmp;
        }
        int ans = 0;
        for (int i = 1; i <= r; ++i) {
            ans = Math.max(ans, prev[i]);
        }
        System.out.println(ans);
    }

    /** 快读 */
    static int read() throws IOException {
        int x = 0, t = 1;
        int ch = System.in.read();
        while (ch < '0' || ch > '9') {
            if (ch == '-') t = -1;
            ch = System.in.read();
        }
        while (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = System.in.read();
        }
        return x * t;
    }

}

部落

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式

输入在第一行给出一个正整数 N（≤ 10⁴），是已知小圈子的个数。随后 N 行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中 K 是小圈子里的人数，P[i]（i = 1, ⋯, K）是小圈子里每个人的编号。这里所有人的编号从 1 开始连续编号，最大编号不会超过 10⁴。

之后一行给出一个非负整数 Q（≤ 10⁴），是查询次数。随后 Q 行，每行给出一对被查询的人的编号。

输出格式

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

题解

使用并查集即可解决。PTA 上无法使用 Java 通过这道题。

public class Main {

    static int[] box = new int[10001];

    static int find(int a) {
        return box[a] == a ? a : (box[a] = find(box[a]));
    }

    static void merge(int a, int b) {
        box[find(a)] = find(b);
    }

    public static void main(String[] args) throws IOException {
        for (int i = 1; i != 10001; ++i) box[i] = i;
        boolean[] flag = new boolean[10001];
        int[] input = new int[10001];
        int n = read();
        // 读入并处理部落信息
        for (int i = 0; i != n; ++i) {
            int k = read();
            for (int j = 0; j != k; ++j) {
                input[j] = read();
                flag[input[j]] = true;
                for (int x = 0; x <= j; ++x) merge(input[x], input[j]);
            }
        }
        // 统计人数和互不相干的部落的数量
        boolean[] tmp = new boolean[10001];
        int size = 0, amount = 0;
        for (int i = 0; i < flag.length; i++) {
            if (flag[i]) {
                ++size;
                if (!tmp[find(i)]) {
                    tmp[find(i)] = true;
                    ++amount;
                }
            }
        }
        System.out.printf("%d %d\n", size, amount);
        int q = read();
        // 检查两个人是否有关系
        for (int i = 0; i != q; ++i) {
            int a = read(), b = read();
            System.out.println(find(a) == find(b) ? 'Y' : 'N');
        }
    }

    /** 不考虑负数的快读 */
    static int read() throws IOException {
        int x = 0;
        int ch = System.in.read();
        while (ch < '0' || ch > '9') {
            ch = System.in.read();
        }
        while (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = System.in.read();
        }
        return x;
    }

}

最短工期

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式

首先第一行给出两个正整数：项目里程碑的数量 N（≤ 100）和任务总数 M。这里的里程碑从 0 到 N − 1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑任务结束里程碑工作时长”，三个数字均为非负整数，以空格分隔。

输出格式

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出“Impossible”。

题解

经典的拓扑图问题，但是题意不是很好理解，这里先说明下题意。

题意简单说就是现在给了我们一个有向有权图，只有一个节点的入度为 0 时才可以从这个节点到达下一个节点，否则必须等待入度变为 0。同时多个任务是可以并行执行的，这点可以从示例中看出来。

打个比方，我们现在有三个里程碑，按照题目的输入格式表示如下：

只有 0 的入度为 0，所以从 0 开始并行执行前两个任务
任务 2 先完成，此时消耗时间为 5，1 的入度变为 1，因为入度不为 0，所以不能执行任务 3
随后任务 1 完成，此时消耗时间为 10，1 的入度变为 0，此时开始执行任务 3
任务 3 完成，耗时 13

理解了题意就好办了，直接给出代码：

public class Main {

    public static void main(String[] args) throws IOException {
        int n = read(), m = read();
        int[] intake = new int[n];
        Map<Integer, List<Pair>> graph = new TreeMap<>();
        for (int i = 0; i != m; ++i) {
            int start = read(), end = read();
            int time = read();
            ++intake[end];
            graph.computeIfAbsent(start, it -> new LinkedList<>()).add(new Pair(end, time));
        }
        int[] time = new int[n];
        while (!graph.isEmpty()) {
            boolean flag = true;
            for (int i = 0; i != n; ++i) {
                if (intake[i] == 0) {
                    intake[i] = -1;
                    List<Pair> list = graph.remove(i);
                    if (list == null) continue;
                    flag = false;
                    for (Pair pair : list) {
                        int end = pair.end;
                        --intake[end];
                        time[end] = Math.max(time[end], time[i] + pair.time);
                    }
                }
            }
            if (flag) break;
        }
        if (!graph.isEmpty()) System.out.println("Impossible");
        else {
            int ans = 0;
            for (int i : time) {
                if (i > ans) ans = i;
            }
            System.out.println(ans);
        }
    }

    /** 不考虑负数的快读 */
    static int read() throws IOException {
        int x = 0;
        int ch = System.in.read();
        while (ch < '0' || ch > '9') {
            ch = System.in.read();
        }
        while (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = System.in.read();
        }
        return x;
    }

}

class Pair {

    int end, time;

    Pair(int end, int time) {
        this.end = end;
        this.time = time;
    }

}

创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o