第 14 届蓝桥杯省赛 Java A 组 Q1~Q3 题解

第 14 届蓝桥杯省赛 Java A 组 Q1~Q3 题解

Q1 特殊日期

算法原理： 暴力枚举 时间复杂度 O(1)。枚举每个年份、每个月份、每个天数，算出各个数位上的总和进行比较。其中 2 月份比较特殊，按照闰年的计算规则：四年一闰，百年不闰，四百年再闰。 判断闰年代码：(i%4==0&&i%100!=0)||(i%400==0)

Q2 与或异或

算法原理： 递归、搜索与回溯 时间复杂度 O(3¹⁰)。将题目的示例转化成数组。我们发现第 1 行第 1 个元素是由第 0 行第 1 个元素和第 0 行第 2 个元素决定的，以此类推。大规模的问题可以分成相似的子问题来解决，采用递归解法。由于针对每两个数有 3 种选择方式：&、|、^，因此要采用回溯的方法来逐个尝试当前位置分别采用 &、|、^得出的结果。这里类似用到了隐式回溯，因为在数组中可以直接覆盖掉数据，达到'回溯'的效果。

显式回溯与隐式回溯的区别： 底层都是回溯思想，只是写法随容器变而已。 ①固定长度结构（char[]、数组）→ 天然适合隐式回溯，写法更干净。 ②变长结构（StringBuffer、List、Builder）→ 必须显式回溯，不然必错。

具体步骤： Ⅰ按题目要求初始化第 0 行。 Ⅱdfs 方法设计： ①如果到了第 5 行，说明第 4 行第一个数即为结果，如果是 1，方案数 +1。 ②填写当前位置 ret[i][j] 的值：取决于 ret[i-1][j] 和 ret[i-1][j+1]。分别填写 ret[i-1][j]&ret[i-1][j+1]、ret[i-1][j] | ret[i-1][j+1]、ret[i-1][j]^ret[i-1][j+1] 的结果。 ③填写完后判断当前位置是否是当前行的最后一个位置。如果是最后一个位置：开启下一行，从第 1 个位置开始填，否则就继续填当前行的下一个位置。

Q3 平均

算法原理： 贪心 时间复杂度 O(n logn)。思路很简单，我们要保证 09 每个数都出现 n/10 次，那么为了保证总的代价和最小，肯定要移除代价小的。因此我们做出决定： ①用大小为 10 的数组表示数字 09，将它们出现的代价挂在后面。 ②为了保留代价大的，移除代价小的，通过降序排序实现。

关键易错点复盘： ①创建大小为 10 的数组，其中每个元素是一个顺序表（此题的形式）：及时初始化，创建空顺序表。 ②创建一个顺序表，其中每个元素是大小为 10 的数组：及时初始化，添加数组。

Java 代码

Q1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int ret = 0;
        for (int i = 1900; i < 9999; i++) { // 枚举年份
            // 计算年份各位的和
            String s  i + ;
               ;
             ( c : s.toCharArray()) sum += c - ;
             (   ; j <= ; j++) { 
                   ; 
                 (j ==  || j ==  || j ==  || j ==  || j ==  || j ==  || j == ) n = ;
                  (j == ) {
                    
                       (i %  ==  && i %  != ) || (i %  == );
                     (isleap) n = ;
                    
                     n = ;
                }  n = ;
                 (   ; k <= n; k++) {
                     (sum == getsum(j) + getsum(k)) ret++;
                }
            }
        }
        System.out.println(ret);
    }

    
        {
           ;
         (n > ) {
            ret += n % ;
            n /= ;
        }
         ret;
    }
}