2021年第十二届蓝桥杯省赛Java B组真题及详细题解

A试题 : ASC【填空题】

本题总分: 5 分

【1、问题描述】

已知大写字母 A 的 ASCII 码为 65,请问大写字母 L 的 ASCII 码是多少?

【2、答案提交】

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

【3、解题思路】

ASCII 码,其中大写字母 A 的 ASCII 码为 65。由于 L 在字母表中在 A 的后面,因此它的 ASCII 码应该比 A 的 ASCII 码大。根据字母表的顺序,L 的 ASCII 码应该为 65 + 11 = 76。因此,大写字母 L 的 ASCII 码为 76。

【4、答案】

76

B试题 : 卡片【填空题】

本题总分: 5 分

【1、问题描述】

小蓝有很多数字卡片,每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数,他想从 1 开始拼出正整数,每拼一个, 就保存起来,卡片就不能用来拼其它数了。 小蓝想知道自己能从 1 拼到多少。 例如,当小蓝有 30张卡片,其中 0 到 9 各 3 张,则小蓝可以拼出 1 到 10, 但是拼 11 时卡片 1 已经只有一张了,不够拼出 11。 现在小蓝手里有 0到 9的卡片各 2021 张,共 20210 张,请问小蓝可以从 1拼到多少?

提示:建议使用计算机编程解决问题

【2、答案提交】

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

【3、解题思路】

这道题可以使用贪心算法来解决。

首先,我们需要将每个数字的卡片数量按照从大到小的顺序排序。这样,我们在拼数字时,就可以尽可能地使用卡片数量更多的数字卡片来拼出当前数字。

然后,我们从数字 1 开始,依次尝试拼出每个数字。对于每个数字,我们将它转换成字符串,然后遍历字符串中的每个字符。对于每个字符,我们检查对应数字的卡片数量是否大于 0。如果大于 0,则将对应卡片数量减 1,并继续检查下一个字符。如果小于等于 0,则说明无法拼出当前数字,我们就停止往后拼数字,因为后面的数字肯定更大,需要的卡片数量也更多。

当我们无法拼出当前数字时,我们就可以退出循环,输出最大能拼出的数字。

【4、代码题解】

public class Main {
    public static void main(String[] args) {
        int[] cards = new int[10];
        Arrays.fill(cards, 2021);  // 初始化每张卡片的数量为 2021
        int num = 1;  // 从 1 开始拼数
        while (true) {
            String s = Integer.toString(num);  // 将数字转换为字符串
            boolean flag = true;  // 标记能否拼出当前数字
            for (char c : s.toCharArray()) {
                int digit = c - '0';  // 获取当前数字
                if (cards[digit] == 0) {  // 如果当前数字的卡片数量为 0,则无法拼出当前数字
                    flag = false;
                    break;
                }
                cards[digit]--;  // 拼出当前数字后,将对应卡片数量减 1
            }
            if (flag) {  // 如果能够拼出当前数字,则尝试拼下一个数字
                num++;
            } else {  // 如果无法拼出当前数字,则退出循环
                break;
            }
        }
        System.out.println(num-1);  // 输出最大能拼出的数字
    }
}

【5、答案】

3181

C试题 : 直线【填空题】

本题总分: 10 分

【1、问题描述】

在平面直角坐标系中,两点可以确定一条直线。如果有多点在一条直线上,
那么这些点中任意两点确定的直线是同一条。
给定平面上 2 × 3 个整点 {(x,y)|0 ≤ x < 2,0 ≤ y < 3, x ∈ Z,y ∈ Z},即横坐标
是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数
的点。这些点一共确定了 11 条不同的直线。
给定平面上 20 × 21 个整点 {(x,y)|0 ≤ x < 20,0 ≤ y < 21, x ∈ Z,y ∈ Z},即横
坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之
间的整数的点。请问这些点一共确定了多少条不同的直线。

【2、答案提交】

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

【3、解题思路】

以上解题思路是枚举所有点对,计算它们之间的斜率,最后将斜率相同的直线视为同一条直线。

具体的解题思路如下:

  1. 枚举所有点对

首先,我们需要枚举所有的点对,即平面上所有不同的点对。这里可以使用两个 for 循环来实现:

然后将平面上所有的点添加到一个 Set 集合中。

  1. 计算斜率

接下来,我们需要计算点对之间的斜率。对于两个点 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) ( x 2 , y 2 ) (x_2, y_2) (x2,y2),它们之间的斜率为 y 2 − y 1 x 2 − x 1 \frac{y_2 - y_1}{x_2 - x_1} x2x1y2y1。但是,如果 x 1 = x 2 x_1 = x_2 x1=x2,则斜率不存在。因此,我们需要对这种情况进行特判。

对于每个点对,我们可以使用一个双重循环来计算它们之间的斜率

  1. 去重

最后,我们需要对斜率相同的直线进行去重。这里我们可以使用一个 Set 集合来存储所有不同的直线。

最终,我们只需要输出 Set 集合的大小,即为不同直线的数量。

完整代码如下:

【4、代码题解】

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<List<Integer>> points = new HashSet<>();  // 平面上的点集
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < 21; j++) {
                points.add(Arrays.asList(i, j));  // 添加平面上的点
            }
        }
        Set<List<Integer>> lines = new HashSet<>();  // 直线的集合
        for (List<Integer> p1 : points) {
            for (List<Integer> p2 : points) {
                if (p1.equals(p2)) continue;  // 如果两个点相同,则跳过
                int dx = p2.get(0) - p1.get(0);  // 计算斜率的分子
                int dy = p2.get(1) - p1.get(1);  // 计算斜率的分母
                int gcd = gcd(dx, dy);  // 计算分子和分母的最大公约数
                List<Integer> line = Arrays.asList(dx / gcd, dy / gcd);  // 表示直线的斜率
                lines.add(line);  // 将直线添加到集合中
            }
        }
        System.out.println(lines.size());  // 输出不同直线的数量
    }

    // 计算两个数的最大公约数
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

【5、答案】

40257

D试题 : 货物摆放【填空题】

本题总分: 10 分

【1、问题描述】

现在,小蓝有 n箱货物要摆放在仓库,每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向,每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足n=L×W×H

给定 n,请问有多少种堆放货物的方案满足要求。

例如,当 n = 4 时,有以下 6 种方案:1×1×4、1×2×2、1×4×1、2×1×2、2 × 2 × 1、4 × 1 × 1。

请问,当 n = 2021041820210418(注意有 16位数字)时,总共有多少种方案?

提示:建议使用计算机编程解决问题。

【2、答案提交】

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

【3、解题思路】

这个问题是一个经典的组合数学问题,可以用数学公式解决。以下是解题思路:

  1. 首先,将 n n n 分解成 L × W × H L \times W \times H L×W×H 的形式,其中 L L L W W W H H H 分别表示长、宽、高。

  2. 由于长、宽、高互相垂直,因此可以假设 L ≥ W ≥ H L \geq W \geq H LWH,从而减少重复计算。

  3. 枚举 L L L W W W H H H,计算满足条件的方案数。具体来说,可以枚举 L L L W W W,然后计算 H H H。如果 L × W × H L \times W \times H L×W×H 等于 n n n,则说明这个方案满足条件。

  4. 对于每个满足条件的方案,计算组合数。具体来说,可以先将 L L L W W W H H H 排序,然后将它们插入到一个长度为 L + W + H − 3 L+W+H-3 L+W+H3 的数组中,其中 L − 1 L-1 L1 个位置插入 L L L W − 1 W-1 W1 个位置插入 W W W H − 1 H-1 H1 个位置插入 H H H。这样,就得到了一个长度为 L + W + H − 3 L+W+H-3 L+W+H3 的排列,从中选择 L − 1 L-1 L1 个位置插入 L L L W − 1 W-1 W1 个位置插入 W W W,就得到了一个长度为 L + W + H − 3 L+W+H-3 L+W+H3 的组合,即 C L + W + H − 3 L − 1 × C W + H − 2 W − 1 C_{L+W+H-3}^{L-1} \times C_{W+H-2}^{W-1} CL+W+H3L1×CW+H2W1

  5. 对于每个满足条件的方案,累加组合数,最后得到的结果就是方案数。

总的来说,这个问题的难点在于如何计算组合数。如果使用组合数学的知识,可以得到一个简单而有效的计算方法。

【4、代码题解】

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger n = new BigInteger("2021041820210418");

        // 计算立方体根号
        BigInteger root = root(n, 3);

        BigInteger cnt = BigInteger.ZERO; // 方案数

        // 枚举长、宽、高
        for (BigInteger l = BigInteger.ONE; l.compareTo(root) <= 0; l = l.add(BigInteger.ONE)) {
            for (BigInteger w = l; w.multiply(l).compareTo(n) <= 0; w = w.add(BigInteger.ONE)) {
                BigInteger h = n.divide(l.multiply(w)); // 计算高
                if (l.multiply(w).multiply(h).equals(n)) { // 验证是否满足条件
                    BigInteger c = C(l.add(w).add(h).subtract(BigInteger.valueOf(3)), l.subtract(BigInteger.ONE))
                            .multiply(C(w.add(h).subtract(BigInteger.valueOf(2)), w.subtract(BigInteger.ONE))); // 计算组合数
                    cnt = cnt.add(c); // 累加方案数
                }
            }
        }

        System.out.println(cnt);
    }

    // 计算组合数
    public static BigInteger C(BigInteger n, BigInteger m) {
        BigInteger res = BigInteger.ONE;
        for (BigInteger i = BigInteger.ZERO; i.compareTo(m) < 0; i = i.add(BigInteger.ONE)) {
            res = res.multiply(n.subtract(i)).divide(i.add(BigInteger.ONE));
        }
        return res;
    }

    // 计算整数的 k 次方根,采用二分法
    public static BigInteger root(BigInteger n, int k) {
        BigInteger lo = BigInteger.ZERO, hi = n;
        while (lo.compareTo(hi) < 0) {
            BigInteger mid = lo.add(hi).add(BigInteger.ONE).divide(BigInteger.valueOf(2));
            if (mid.pow(k).compareTo(n) > 0) {
                hi = mid.subtract(BigInteger.ONE);
            } else {
                lo = mid;
            }
        }
        return lo;
    }
}

【5、答案】

2430

E试题 : 路径【填空题】

本题总分: 15 分

【1、问题描述】

小蓝学习了最短路径之后特别高兴,他定义了一个特别的图,希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成,依次编号 1 至 2021。

对于两个不同的结点 a, b,如果 a 和 b 的差的绝对值大于 21,则两个结点 之间没有边相连;如果 a 和 b 的差的绝对值小于等于 21,则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如:结点 1 和结点 23 之间没有边相连;结点 3 和结点 24 之间有一条无 向边,长度为 24;结点 15 和结点 25 之间有一条无向边,长度为 75。

请计算,结点 1 和结点 2021 之间的最短路径长度是多少。

提示:建议使用计算机编程解决问题。

【2、答案提交】

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

【3、解题思路】

题目要求计算结点 1 和结点 2021 之间的最短路径长度,可以使用 Dijkstra 算法求解。

首先需要初始化结点之间的距离,对于两个结点 i 和 j,如果它们的差的绝对值大于 21,则它们之间没有边相连;否则,它们之间有一条长度为它们的最小公倍数的无向边相连。

在 Dijkstra 算法中,需要维护一个集合 S,表示已经找到最短路径的结点集合,以及一个数组 d,表示每个结点到起点的最短距离。初始时,集合 S 中只包含起点,数组 d 中只有起点的距离为 0,其它结点的距离为无穷大。

每次从未加入集合 S 的结点中选择距离起点最近的结点 u,将其加入集合 S,并更新与结点 u 相连的结点 v 的距离,即:

d[v] = min(d[v], d[u] + w(u, v))

其中 w(u, v) 表示结点 u 和结点 v 之间的距离。在本题中,w(u, v) 等于结点 u 和结点 v 的最小公倍数。

重复上述过程,直到结点 2021 加入集合 S,此时数组 d 中的值即为结点 1 到结点 2021 的最短路径长度。

由于本题中结点的数量较小,因此可以直接使用 HashMap 存储结点之间的距离,而不需要使用邻接矩阵或邻接表等数据结构。

【4、代码题解】

import java.util.*;

public class Main {
    static final int N = 2021;
    static final int INF = 0x3f3f3f3f;

    static int[] d = new int[N]; // 存储结点到起点的距离
    static boolean[] vis = new boolean[N]; // 标记结点是否已经加入集合 S
    static Map<Integer, Map<Integer, Integer>> g = new HashMap<>(); // 存储结点之间的距离

    // 求两个数的最大公约数
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 求两个数的最小公倍数
    static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    // Dijkstra 算法求解最短路径
    static void dijkstra() {
        // 使用 PriorityQueue 来维护未加入集合 S 的结点中距离起点最近的结点
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{1, 0}); // 起点到起点的距离为 0
        d[1] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0], dist = curr[1];

            if (vis[u]) continue;
            vis[u] = true;

            if (u == N - 1) break; // 已经到达终点

            // 枚举与结点 u 相连的结点
            Map<Integer, Integer> neighbors = g.getOrDefault(u, new HashMap<>());
            for (int v : neighbors.keySet()) {
                int w = neighbors.get(v);
                if (vis[v]) continue;
                int newDist = dist + w;
                if (newDist < d[v]) {
                    d[v] = newDist;
                    pq.offer(new int[]{v, newDist});
                }
            }
        }
    }

    public static void main(String[] args) {
        // 初始化结点之间的距离
        for (int i = 1; i <= N; i++) {
            Map<Integer, Integer> neighbors = new HashMap<>();
            for (int j = i + 1; j <= N; j++) {
                if (Math.abs(i - j) > 21) continue;
                int w = lcm(i, j);
                neighbors.put(j, w);
            }
            g.put(i, neighbors);
        }

        Arrays.fill(d, INF); // 初始化距离为无穷大
        dijkstra(); // 求解最短路径

        System.out.println(d[N - 1]); // 输出结点 1 到结点 2021 的最短路径长度
    }
}

【5、答案】

10266837

F试题 : 时间显示 【编程题】

时间限制: 1.0s 内存限制: 512.0MB 本题总分: 15 分

【问题描述】

小蓝要和朋友合作开发一个时间显示的网站。

在服务器上,朋友已经获取了当前的时间,用一个整数表示,值为从 19701970 年 11 月 11 日 00:00:0000:00:00 到当前时刻经过的毫秒数。

现在,小蓝要在客户端显示出这个时间。小蓝不用显示出年月日,只需要显示出时分秒即可,毫秒也不用显示,直接舍去即可。

给定一个用整数表示的时间,请将这个时间对应的时分秒输出。

【输入格式】:

输入一行包含一个整数,表示时间。

【输出格式】:`

输出时分秒表示的当前时间,格式形如 HH:MM:SS,其中 HH 表示时,值为 00 到 2323,MM 表示分,值为 00 到 5959,SS 表示秒,值为 00 到 5959。时、分、秒 不足两位时补前导 00。

【样例输入1】

46800999

【样例输出1】

13:00:00

【样例输入2】

1618708103123

【样例输出2】

01:08:23

【评测用例规模与约定】

对于所有评测用例,给定的时间为不超过 10的18次方的正整数。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 512M

【解题思路】

代码思路:

  1. 首先读入时间,题目中给定的时间是UTC时间,单位为毫秒。

  2. 根据题意,我们需要计算出当前时间对应的小时、分钟和秒数。我们可以先计算出总共经过的小时数,即 time / 3600000,然后用余数计算出分钟数,即 (time % 3600000) / 60000,最后用余数计算出秒数,即 (time % 60000) / 1000

  3. 输出结果,注意时、分、秒不足两位时需要在前面补上 0。

时间复杂度: O ( 1 ) O(1) O(1)

【代码题解】

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读入时间,单位为毫秒
        int time = sc.nextInt();

        // 计算小时、分钟和秒数
        int hour = time / 3600000 % 24; // 对24取模,得到小时数
        int minute = (time % 3600000) / 60000; // 取余数,得到分钟数,再除以60得到分钟数
        int second = (time % 60000) / 1000; // 取余数,得到秒数,再除以1000得到秒数

        // 输出结果,注意时、分、秒不足两位时需要在前面补上 0
        System.out.printf("%02d:%02d:%02d", hour, minute, second);
    }
}

G试题 : 最少砝码【编程题】

时间限制: 1.0s 内存限制: 512.0MB 本题总分: 20 分

【问题描述】

你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意 小于等于 N的正整数重量。

那么这套砝码最少需要包含多少个砝码?

注意砝码可以放在天平两边。

【输入格式】:

输入包含一个正整数 N。

【输出格式】:`

输出一个整数代表答案。

【样例输入】

7

【样例输出】

3

【评测用例规模与约定】

对于所有评测用例,1 ≤ N ≤ 1000000000。

【样例说明】

33 个砝码重量是 1、4、6,可以称出 1 至 7的所有重量。

1 = 1;

2 = 6 − 4(天平一边放 66,另一边放 44);

3 = 4 − 1;

4 = 4;

5 = 6 − 1;

6 = 6;

7 = 1 + 6;

少于 3 个砝码不可能称出 1 至 7 的所有重量。

【解题思路】

算法思路

本题是一道贪心算法的经典题目。我们需要设计一套砝码,使得利用这些砝码可以称出任意小于等于N的正整数重量,且砝码最少。

首先,我们考虑最小的砝码,显然是1,因为1可以表示任意小于等于1的正整数。接下来,我们考虑如何设计更多的砝码。我们发现,如果我们有了一个砝码w,那么我们可以通过以下两种方式得到更多的砝码:

  • 在w的基础上增加一个和w相等的砝码;
  • 在w的基础上增加一个和w之和相等的砝码。

例如,如果我们已经有了一个砝码6,那么我们可以通过以下两种方式得到更多的砝码:

  • 增加一个砝码6,这样我们就有了两个6的砝码,可以表示任意小于等于12的正整数;
  • 增加一个砝码10,这样我们就有了6和10两个砝码,可以表示任意小于等于16的正整数。

因此,我们可以从小到大枚举每个正整数,对于每个正整数i,我们都尝试用已有的砝码表示出来。如果无法表示,则需要添加一个新的砝码,这个砝码的重量就是i减去已有砝码可以表示的最大重量。

具体来说,我们可以维护一个变量max_weight,表示当前已有砝码可以表示的最大重量。对于每个正整数i,如果i可以用已有砝码表示出来,则什么也不做;如果无法表示,则需要添加一个新的砝码,这个砝码的重量就是i减去max_weight。

最后,我们需要注意一下特殊情况,即N=1时,答案为1。

【代码题解】

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n == 1) { // 特判:当n=1时,答案为1
            System.out.println(1);
        } else {
            int ans = 1; // 记录砝码的数量,初始值为1,因为最小的砝码是1
            int max_weight = 1; // 记录当前已有砝码可以表示的最大重量,初始值为1
            while (max_weight < n) { // 当已有砝码可以表示的最大重量小于n时,继续添加砝码
                ans++; // 砝码数量加1
                max_weight = 2 * max_weight + 1; // 新砝码的重量是已有砝码可以表示的最大重量加1
            }
            System.out.println(ans); // 输出答案
        }
    }
}

H试题 : 杨辉三角形【编程题】

时间限制: 1.0s 内存限制: 512.0MB 本题总分: 20 分

【问题描述】

下面的图形是著名的杨辉三角形:

image

如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列: 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯

给定一个正整数 N,请你输出数列中第一次出现 N是在第几个数?

输入描述

输入一个整数 N

输出描述

输出一个整数代表答案。

输入输出样例

示例 1

输入

6

输出

13

评测用例规模与约定

对于 2020 的评测用例,1≤N≤10; 对于所有评测用例,1≤N≤1000000000

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

【解题思路】

题目要求我们输出数列中第一次出现 N 的位置,其中数列是杨辉三角形按从上到下、从左到右的顺序排列的。因此,我们可以先构建杨辉三角形,然后遍历这个数组,找到第一次出现 N 的位置。

构建杨辉三角形的方法是,从第二行开始,每一行的第一个数和最后一个数都是 1,中间的数等于上一行对应位置的数和上一行对应位置前一个数的和。我们可以用一个二维数组来存储杨辉三角形。

遍历数组时,我们可以用一个计数器记录当前的位置,遇到第一次出现 N 的数时,输出计数器的值即可。

时间复杂度: O ( N 2 ) O(N^2) O(N2)

空间复杂度: O ( N 2 ) O(N^2) O(N2)

【代码题解】

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 构建杨辉三角形
        int[][] triangle = new int[n][n];
        for (int i = 0; i < n; i++) {
            triangle[i][0] = 1; // 每一行的第一个数都是1
            triangle[i][i] = 1; // 每一行的最后一个数都是1
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]; // 中间的数等于上一行对应位置的数和上一行对应位置前一个数的和
            }
        }

        // 遍历数组找到第一次出现N的位置
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                count++;
                if (triangle[i][j] == n) {
                    System.out.println(count);
                    return;
                }
            }
        }
    }
}

I试题 : 双向排序【编程题】

https://www.lanqiao.cn/problems/1458/learning/

J试题 :括号序列 【编程题】

时间限制: 1.0s 内存限制: 512.0MB 本题总分: 25 分

【问题描述】

给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。

例如,对于括号序列 ((()(((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:()()()()()()、()(())()(())、(())()(())()、(()())(()()) 和 ((()))((()))。

【输入格式】:

输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和右括号。

【输出格式】:`

输出一个整数表示答案,答案可能很大,请输出答案除以 10000000071000000007 (即 109+7)109+7) 的余数。

【样例输入】

((()

【样例输出】

5

【评测用例规模与约定】

对于 4040 的评测用例,∣s∣≤200。

对于所有评测用例,1≤∣s∣≤5000。

【解题思路】

本题是一个动态规划问题。

目标是添加最少的括号使得序列合法,显然,添加的括号数量越少,其本质不同的情况就会越少。

因此,考虑定义状态: f [ i ] [ j ] f[i][j] f[i][j] 表示将区间 [ i , j ] [i,j] [i,j] 变为合法括号序列所添加的最少括号数。

接下来,考虑状态转移方程:

  • s [ i ] = ′ ( ′ s[i]='(' s[i]=( s [ j ] = ′ ) ′ s[j]=')' s[j]=) 时, f [ i ] [ j ] = f [ i + 1 ] [ j − 1 ] f[i][j]=f[i+1][j-1] f[i][j]=f[i+1][j1]
  • s [ i ] = ′ ( ′ s[i]='(' s[i]=( s [ j ] = ′ ( ′ s[j]='(' s[j]=( 时,可以在 j j j 位置添加一个 ‘)’,则 f [ i ] [ j ] = f [ i ] [ j − 1 ] + 1 f[i][j]=f[i][j-1]+1 f[i][j]=f[i][j1]+1
  • s [ i ] = ′ ) ′ s[i]=')' s[i]=) s [ j ] = ′ ) ′ s[j]=')' s[j]=) 时,可以在 i i i 位置添加一个 ‘(’,则 f [ i ] [ j ] = f [ i + 1 ] [ j ] + 1 f[i][j]=f[i+1][j]+1 f[i][j]=f[i+1][j]+1
  • s [ i ] = ′ ) ′ s[i]=')' s[i]=) s [ j ] = ′ ( ′ s[j]='(' s[j]=( 时,可以在 j j j 位置添加一个 ‘)’,也可以在 i i i 位置添加一个 ‘(’,取两种情况的较小值,即 f [ i ] [ j ] = min ⁡ ( f [ i + 1 ] [ j ] + 1 , f [ i ] [ j − 1 ] + 1 ) f[i][j]=\min(f[i+1][j]+1,f[i][j-1]+1) f[i][j]=min(f[i+1][j]+1,f[i][j1]+1)

考虑边界情况,当 i = j i=j i=j 时, f [ i ] [ j ] = 1 f[i][j]=1 f[i][j]=1

最后,答案为 f [ 1 ] [ n ] f[1][n] f[1][n]

时间复杂度: O ( n 2 ) O(n^2) O(n2)

【代码题解】

import java.util.Scanner;

public class Main {

    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().trim(); // 读入字符串
        int n = s.length(); // 字符串长度
        int[][] f = new int[n+1][n+1]; // 定义状态数组 f
        for (int i = 1; i <= n; i++) {
            f[i][i] = 1; // 初始化状态,当区间长度为 1 时,不需要添加括号
        }
        for (int len = 2; len <= n; len++) { // 枚举区间长度
            for (int i = 1; i <= n-len+1; i++) { // 枚举区间左端点
                int j = i + len - 1; // 区间右端点
                if (s.charAt(i-1) == '(' && s.charAt(j-1) == ')') { // 情况1:s[i]='(',s[j]=')'
                    f[i][j] = f[i+1][j-1]; // 不需要添加括号
                } else {
                    f[i][j] = Math.min(f[i+1][j], f[i][j-1]) + 1; // 情况2和情况3:添加括号
                    if (s.charAt(i-1) == '(' && s.charAt(j-1) == '(') { // 情况2:s[i]='(',s[j]='('
                        f[i][j] = Math.min(f[i][j], f[i][j-1]+1); // 在 j 位置添加一个 ')'
                    } else if (s.charAt(i-1) == ')' && s.charAt(j-1) == ')') { // 情况3:s[i]=')',s[j]=')'
                        f[i][j] = Math.min(f[i][j], f[i+1][j]+1); // 在 i 位置添加一个 '('
                    }
                }
            }
        }
        System.out.println(f[1][n] % MOD); // 输出答案
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/5897.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

二十、Javascript API(一)

1. Atomics和SharedArrayBuffer 多个上下文访问 SharedArrayBuffer时&#xff0c;如果同时对缓冲区执行操作&#xff0c;就可能出现资源争用问题。Atomics API 通过强制同一时刻只能对缓冲区执行一个操作&#xff0c;可以让多个上下文安全地读写一个SharedArrayBuffer。 1.1 …

Android HTTP请求方式

1.HttpClient使用流程 基本流程&#xff1a; 2.HttpClient使用示例 1&#xff09;使用HttpClient发送GET请求 直接贴下简单的发送Get请求的代码&#xff1a; public class MainActivity extends Activity implements OnClickListener { private Button btnGet; private WebV…

STM-32:GPIO 输出-点亮LED-流水灯-蜂鸣器

目录一、GPIO1.1GPIO简介1.2GPIO 硬件解析1.2.1保护二极管1.2.2 P-MOS、N-MOS 管1.2.3数据输入输出寄存器1.2.4复用功能输出1.2.5模拟输入输出1.3GPIO 的工作模式1.3.1 输入模式 (模拟/浮空/上拉/下拉)1.3.2 输出模式 (推挽/开漏)1.3.3 复用功能 (推挽/开漏)1.3.4 小结二、GPIO…

ChatGPT将引发大量而普遍的网络安全隐患

ChatGPT是一个基于人工智能的语言生成模型&#xff0c;它可以在任何给定的时间&#xff0c;使用自然语言生成技术&#xff0c;生成文本、对话和文章。它不仅可以被用来编写文本&#xff0c;还可以用来编写语言、生成图像和视频。目前&#xff0c; ChatGPT已广泛应用于语言翻译、…

【数据结构篇】-树(共计两万字,你真的搞懂了它吗)

友情链接&#xff1a;【数据结构与算法】首篇 - 思维导图 - 各部分内容目录 文章目录&#x1f680;树&#x1f6a2;一、树的原理精讲&#xff08;一&#xff09;树的定义&#xff08;二&#xff09;基本术语&#xff08;三&#xff09;树的性质&#x1f6a2;二、树的存储结构&a…

C++ STL:stack和queue的使用和底层实现

目录 一. 什么是stack和deque 二. stack和queue的使用方法 2.1 stack的常用接口 2.2 queue的常用接口 三. stack和queue的底层实现原理 3.1 容器适配器 3.2 deque&#xff08;双端队列&#xff09;的概念及抽象结构 3.3 deque的底层实现结构 3.4 deque的优缺点 —— 为…

try... excpet BaseException(异常处理捕获)

try ...except 是最常见的捕获处理异常的结构&#xff0c;其主要作用是将可能出现问题的代码块用try &#xff1a;包裹起来&#xff0c;不至于出现错误让程序崩溃&#xff0c;无法执行下去常见的try ...excpet 的结构有三种try&#xff1a;pass except BaseException as e &…

Azure SQL基础到实战(2)-部署

目录Azure 上的数据库服务的演变Azure SQL 部署选项Azure 虚拟机上的 SQL ServerIaaS 与PaaS无版本数据库服务SQL 托管实例SQL 数据库弹性数据库池Azure 上的数据库服务的演变 Azure SQL 是 Microsoft 作为 Azure 云计算平台的一部分提供的云数据库产品/服务。 与其他版本的 S…

含光热电站、有机有机朗肯循环、P2G的综合能源优化调度(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

算法---扫雷游戏

题目 让我们一起来玩扫雷游戏&#xff01; 给你一个大小为 m x n 二维字符矩阵 board &#xff0c;表示扫雷游戏的盘面&#xff0c;其中&#xff1a; ‘M’ 代表一个 未挖出的 地雷&#xff0c; ‘E’ 代表一个 未挖出的 空方块&#xff0c; ‘B’ 代表没有相邻&#xff08;…

服务器部署前后端分离项目

服务器部署前后端分离项目 文章目录服务器部署前后端分离项目一、安装环境安装jdk1、在/usr/local目录下创建jdk文件夹&#xff0c;并将jdk安装包放到/usr/local/jdk包下并解压2、配置jdk的环境变量3、进行编译&#xff0c;4、检测是否安装成功安装tomcat1、将tomcat放到/usr/l…

Linux内核模块开发之创建slab内存缓存(kmem_cache_*)

Linux内核模块开发之创建slab内存缓存&#xff08;kmem_cache_*&#xff09;一、创建专用的内存缓存编程接口二、实现步骤三、内存缓存的数据结构四、完整代码示例4.1、源代码4.2、编译和执行一、创建专用的内存缓存编程接口 创建内存缓存 kmem_cache_create。指定内存缓存分配…

软件测试零基础好入门么

零基础学习软件测试不失为一个好的选择&#xff0c;虽然IT行业里对小白最友好的非软件测试莫属了&#xff0c;但是也要看你个人在学习软件测试这件事上面花费了多少的时间和努力了~ 每年毕业季&#xff0c;IT行业依然是比较热门且收入是最高的行业。对于应届毕业生来说想要进入…

数据结构学习之路-队列

队列&#xff08;Queue&#xff09;定义队列的接口设计&#xff08;使用双向链表&#xff09;用栈实现队列的接口设计双端队列&#xff08;Deque&#xff09;循环队列&#xff08;Circle Queue&#xff09;循环双端队列&#xff08;Ciecle Deque&#xff09;定义 队列是一种特…

企业短视频推广怎么玩?制造业短视频推广干货分享

短视频作为一种新型营销方式&#xff0c;已经成为企业推广的重要手段。通过合理的推广策略、精美的短视频制作、适当的社交媒体平台选择和与用户的互动&#xff0c;企业可以实现短视频推广的效果。同时&#xff0c;借助短视频制作工具可以提高制作效率和降低制作成本&#xff0…

文件IO知识(一)

作者&#xff1a;爱塔居 专栏&#xff1a;JavaEE 作者简介&#xff1a;大三学生&#xff0c;希望和大家一起进步。 文章目录 目录 文章目录 前言 一、路径 二、文本文件和二进制文件 三、文件系统操作 四、“字符流”和“字节流” 五、utf8和unicode 前言 平时谈到的“文件”&…

Spring 源码解析 - BeanPostProcessor 扩展接口

一、BeanPostProcessor 扩展接口 BeanPostProcessor是Spring中的一个扩展接口&#xff0c;它可以在Spring容器实例化bean之后&#xff0c;在执行 bean的初始化方法前后&#xff0c;允许我们自定义修改新的 bean实例。比如修改 bean 的属性&#xff0c;将 bean 替换为动态代理等…

《Effective Objective-C 2.0 》 阅读笔记 item6

第6条&#xff1a;理解“属性”这一概念 1. 属性的概念 “属性”&#xff08;property&#xff09;是Objective-C的一项特性&#xff0c;用于封装对象中的数据。 Objective-C对象通常会把所需要的数据保存为各种实例变量&#xff0c;实例变量一般通过“存取方法”&#xff08…

GPT-4 免费体验方法

POE 在Quora上非常受欢迎的手机聊天机器人Poe App已经集成ChatGPT助手&#xff01;除了最初集成的三个聊天机器人Sage、Claude和Dragonfly外&#xff0c;Poe现在还加入了第四位ChatGPT。由于使用了ChatGPT API&#xff0c;因此Poe拥有真正的ChatGPT。 现在更是第一批集成了GP…

JDK1.8去除永久代引入元空间的原因您知道吗

之前写了一篇文章 JVM中的堆和栈到底存储了什么 重点介绍了Java虚拟机运行时数据区中堆、栈以及方法区存储数据的相关知识很受大家欢迎&#xff0c;今天来介绍一下jdk 1.8开始引入的元空间&#xff0c;元空间的引入也是与Java虚拟机运行时存储数据有关。 元空间 JDK8之后就没…
最新文章