【蓝桥杯备考】第十二届蓝桥杯省赛Java B组真题编程题

本文介绍: 当 s[j] 是左括号时，dp[i][j] = dp[i+1][j-1] + dp[i][j-2] + …我们可以定义一个布尔型的二维数组 dp[i][j]，其中 dp[i][j] 表示前 i 个砝码是否可以组成重量 j。dp[i][j] = dp[i-1][j] || dp[i-1][j-W[i]] || dp[i-1][|j-W[i]|]，其中 || 表示逻辑或。当 s[j] 是右括号时，dp[i][j] = dp[i][j-2] + dp[i+1][j-1] + …+ dp[i][i+1]。

第十二届蓝桥杯省赛Jav a B组真题 编程题

1. 杨辉三角
- 问题描述
2. 时间显示
- 问题描述
3. 双向排序
- 问题描述
4. 括号序列
- 问题描述
- 分析
5.砝码称重
- 分析

1. 杨辉三角

问题描述

著名的杨辉三角形，按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列:
1，1，1，1，2, 1，1, 3, 3, 1，1，4，6, 4，1，…
给定一个正整数N，请你输出数列中第一次出N是在第几个数?

输入格式

输入一个整数N

输出格式

输出一个整数代表答案

样例输入

样例输出

import java.util.Scanner;

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

        int result = findPosition(N);
        System.out.println(result);
    }

    static int findPosition(int target) {
        int row = 1;
        int col = 1;
        int currentValue = 1;

        while (currentValue != target) {
            col++;
            currentValue = calculateValue(row, col);

            if (currentValue > target) {
                row++;
                col = 1;
            }
        }

        return row * (row + 1) / 2 + col;
    }

    static int calculateValue(int row, int col) {
        // 计算杨辉三角形中第 row 行、第 col 列的值
        if (col == 1 || col == row) {
            return 1;
        } else {
            return calculateValue(row - 1, col - 1) + calculateValue(row - 1, col);
        }
    }
}

2. 时间显示

问题描述

小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从1970年1月1日O0:00:00到当前时刻经过的毫秒数。
现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

输入格式

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

输出格式

输出时分秒表示的当前时间，格式形如HH:MM:SS，其中HH表示时，值为О到23，MM表示分，值为О到59，SS表示秒，值为О到59。时、分、秒不足两位时补前导0。

样例输入 1

46800999

输出

13：00：00

样例输入 2

1618708103123

输出

01：08：23

import java.util.Scanner;

public class TimeDisplay {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // System.out.println("请输入一个整数，表示时间：");
        long milliseconds = scanner.nextLong();

        String result = formatTime(milliseconds);
        System.out.println(result);
    }

    static String formatTime(long milliseconds) {
        long totalSeconds = milliseconds / 1000;

        long hours = totalSeconds / 3600;
        long minutes = (totalSeconds % 3600) / 60;
        long seconds = totalSeconds % 60;

        // 格式化时、分、秒，补前导0
        String formattedHours = String.format("%02d", hours);
        String formattedMinutes = String.format("%02d", minutes);
        String formattedSeconds = String.format("%02d", seconds);

        return formattedHours + ":" + formattedMinutes + ":" + formattedSeconds;
    }
}

3. 双向排序

问题描述

给定序列(a1,a2,……,an) = (1,2,…. ,n)，即ai= i
小蓝将对这个序列进行m次操作，每次可能是将a1,a2,.…· ,aqi降序排列，或者将aq,aqi+1,…. ,an升序排列。
请求出操作完成后的序列。

输入格式

输入的第一行包含两个整数n, m，分别表示序列的长度和操作次数。
接下来m行描述对序列的操作，其中第i行包含两个整数 pi,qi表示操作类型和参数。当pi=0时，表示将a1,a2,… ,aqi。降序排列;当pi=1时，表示将aqi,aqi+1,…· ,an升序排列。

输出格式

输出一行，包含n个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

样例输入

3 3

0 3

1 2

0 2

输出

3 1 2

样例说明

原数列为(1,2,3)

第1步后为(3,2,1)

第2步后为(3,1,2)。

第3步后为(3,1,2)

与第2步操作后相同，因为前两个数已经是降序了。

import java.util.Scanner;

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

        // 输入序列长度和操作次数
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 初始化序列数组
        int[] sequence = new int[n];
        for (int i = 0; i < n; i++) {
            sequence[i] = i + 1;
        }

        // 执行操作
        for (int i = 0; i < m; i++) {
            int operationType = scanner.nextInt();
            int q = scanner.nextInt();

            if (operationType == 0) {
                // 降序排列
                reverseArray(sequence, 0, q - 1);
            } else {
                // 升序排列
                reverseArray(sequence, q - 1, n - 1);
            }
        }

        // 输出最终序列
        for (int i = 0; i < n; i++) {
            System.out.print(sequence[i] + " ");
        }
    }

    // 将数组中[start, end]范围内的元素进行翻转
    static void reverseArray(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

4. 括号序列

问题描述

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列（(()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果: ()()()、()(())、(())()、((()）和（(() ) ) 。

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

输出格式

输出一个整数表示答案，答案可能很大，请输出答案除以1000000007(即10的9次方＋7)的余数。

样例输入

（（（）

输出

分析

这个问题可以使用动态规划来解决。定义一个二维数组 dp[i][j] 表示在括号序列的子串 s[i:j] 中，添加若干括号使其合法的方案数。状态转移方程如下：

当 s[j] 是左括号时，dp[i][j] = dp[i+1][j-1] + dp[i][j-2] + … + dp[i][i+2] + dp[i][i+1]。

当 s[j] 是右括号时，dp[i][j] = dp[i][j-2] + dp[i+1][j-1] + … + dp[i][i+1]。

上述方程中的第一项 dp[i+1][j-1] 表示当前右括号与其对应的左括号匹配，后面的项则表示在这之前的某个位置添加若干括号。

import java.util.Scanner;

public class ParenthesesSequence {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // System.out.println("请输入一个括号序列：");
        String s = scanner.nextLine();

        int result = countAdditions(s);
        System.out.println(result);
    }

    static int countAdditions(String s) {
        int mod = 1000000007;
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int len = 2; len <= n; len += 2) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;

                if (s.charAt(j) == '(') {
                    dp[i][j] = dp[i + 1][j - 1];
                    for (int k = i + 2; k <= j; k += 2) {
                        dp[i][j] = (dp[i][j] + dp[i][k - 2] * 1L * dp[k][j]) % mod;
                    }
                } else {
                    for (int k = i + 1; k <= j; k += 2) {
                        dp[i][j] = (dp[i][j] + dp[i][k - 2] * 1L * dp[k][j]) % mod;
                    }
                    dp[i][j] = (dp[i][j] + dp[i + 1][j - 1]) % mod;
                }
            }
        }

        return dp[0][n - 1];
    }
}

5.砝码称重

问题描述

你有一架天平和N个砝码，这N个砝码重量依次是W1,W2，.…. ， WN .请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数N。
第二行包含Ⅳ个整数:W1，W2，W3，… – , WN 。

输出

输出一个整数代表答案

样例输入

1 4 6

输出

样例说明

能称出的10种重量是:1、2、3、4、5、6、7、9、10、11。

1 = 1;
2=6-4(天平一边放6，另一边放4);

3=4-1;

4=4;

5=6- 1;

6=6;

7=1＋6;

9 =4＋6-1;

10=4＋6;

11 =1＋4＋6。

分析

这个问题可以通过动态规划来解决。我们可以定义一个布尔型的二维数组 dp[i][j]，其中 dp[i][j] 表示前 i 个砝码是否可以组成重量 j。

具体的状态转移方程如下：

dp[i][j] = dp[i-1][j] || dp[i-1][j-W[i]] || dp[i-1][|j-W[i]|]，其中 || 表示逻辑或。

初始条件：dp[0][0] = true，表示使用 0 个砝码可以组成重量 0。

最终，我们只需要统计最后一行 dp[N][j] 中为 true 的个数，即可得到可以称出的不同重量的种数。

import java.util.Scanner;

public class WeightMeasurement {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // System.out.println("请输入砝码个数 N：");
        int N = scanner.nextInt();
        int[] weights = new int[N];
        // System.out.println("请输入各个砝码的重量：");
        for (int i = 0; i < N; i++) {
            weights[i] = scanner.nextInt();
        }

        int result = countWeightVarieties(N, weights);
        System.out.println(result);
    }

    static int countWeightVarieties(int N, int[] weights) {
        int sum = 0;
        for (int weight : weights) {
            sum += weight;
        }

        boolean[][] dp = new boolean[N + 1][2 * sum + 1];
        dp[0][sum] = true;

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= 2 * sum; j++) {
                if (j - weights[i - 1] >= 0) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - weights[i - 1]];
                }

                dp[i][j] = dp[i][j] || dp[i - 1][j];
                dp[i][j] = dp[i][j] || dp[i - 1][Math.abs(j - weights[i - 1])];
            }
        }

        int count = 0;
        for (int j = 0; j <= 2 * sum; j++) {
            if (dp[N][j]) {
                count++;
            }
        }

        return count;
    }
}