第十二届蓝桥杯国赛 Java--B组

开摆日寄

6.8

增加了H题的题解，每日提醒一下我是个废物，呜呜呜

5.24

增加了F题的题解，我是大废物

4.28

准备国赛好难吖

试题A: 整数范围(5分)

答案提交

255

分析

签到题，11111111对应的十进制是255

Code

无

试题B: 纯质数(5分)

答案提交

1903

分析

填空题就无脑暴力了，先判断是不是素数，是的话就把整型转为字符串，挨个判断每个字符是不是2 3 5 7，不是的话直接返回false，剩下的返回true。然后sum++;

Code

public class Main {
    public static void main(String[] args) {
        int sum = 0;
        for (int i = 2; i <= 20210605; i++) {
            if (isSushu(i))
                if (isChun(i))
                    sum++;
        }
        System.out.println(sum);
    }

    static boolean isSushu(int i) {
        for (int j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0) return false;
        }
        return true;
    }

    static boolean isChun(int i) {
        char[] chars = (i + "").toCharArray();
        for (char c : chars) {
            if (!(c == '2' || c == '3' || c == '5' || c == '7')) return false;
        }
        return true;
    }
}

试题C: 完全日期(10分)

答案提交

977

分析

用Java的Calendar类可以轻松处理此类问题
用Calendar类的get方法，可以很轻松的获取年月日对应的整型

Calendar获取的月份从0开始，0至11分别对应1月至12月，所以我们的实际月份需要加上1

将calendar设置为2001年1月1日，要算到2021年年底，所以干脆把终止条件写成year < 2022
随后获取每天的年月日，并判断是否符合条件，随后日期加一天

Code

import java.util.Calendar;

public class Main {
    public static void main(String[] args) {
        int sum = 0;
        Calendar calendar = Calendar.getInstance();
        calendar.set(2001, 0, 1);
        int day, month, year = 0;
        while (year < 2022) {
            day = calendar.get(Calendar.DAY_OF_MONTH);
            month = calendar.get(Calendar.MONTH) + 1;
            year = calendar.get(Calendar.YEAR);
            if (judge(year, month, day))
                sum++;
            calendar.add(Calendar.DAY_OF_YEAR, 1);
        }
        System.out.println(sum);
    }

    static boolean judge(int year, int month, int day) {
        char[] chars = ("" + year + month + day).toCharArray();
        int res = 0;
        for (char c : chars) {
            res += c - '0';
        }
        return (int) Math.sqrt(res) * (int) Math.sqrt(res) == res;
    }
}

试题D: 最小权值(10分)

答案提交

2653631372

分析

递推公式已经给出了，我们定义dp[i]表示有i个节点的树的最小权值，dp[0] = 0;我们最终输出dp[2021]即可。
由于我们要找最小值，所以我们事先把 dp 数组初始化为最大值
外层循环i用来遍历所有的节点，内层循环 j 用来遍历 i 的左右子树的所有可能
例如我们要求5个节点的树的最小权值，那么所有的可能为

左边无节点，右边4节点子树，中间一个根节点
左边1节点子树，右边3节点子树，中间一个根节点
左边2节点子树，右边2节点子树，中间一个根节点
左边3节点子树，右边1节点子树，中间一个根节点
左边4节点子树，右边无节点，中间一个根节点

左右两边的子树是相互独立的，所以我们直接套用给出的地推公式即可完成本题
dp[i] = Math.min(dp[i], 1 + 2 * dp[j] + 3 * dp[i - j - 1] + j * j * (i - j - 1));

Code

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        long[] dp = new long[2022];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= 2021; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = Math.min(dp[i], 1 + 2 * dp[j] + 3 * dp[i - j - 1] + j * j * (i - j - 1));
            }
        }
        System.out.println(dp[2021]);
    }
}

试题E: 大写(15分)

分析

这个位置竟然有一道送分题，希望今年出的题简单点

Code

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        System.out.println(str.toUpperCase());
    }
}

试题F: 123(15分)

分析

题目不全，数据量最大是10^12数量级
思路：前缀和，但是我们无法创建一个数组用来存储10^12数量级的前缀和
但这道题是有规律的，我们可以间接的计算出前缀和

1 --> 这一行的前缀和是 1 ; 这一行及之前共有 1 个数
1 2 --> 这一行的前缀和是 4 ; 这一行及之前共有 3 个数
1 2 3 --> 这一行的前缀和是 10 ; 这一行及之前共有 6 个数
1 2 3 4 --> 这一行的前缀和是 20 ; 这一行及之前共有 10 个数
1 2 3 4 5
以这个为例，我们要求前13个数字前缀和，也就是第5行的第3个及之前的前缀和

我们可以用上一行的前缀和20，再加上从1至3的和

归纳一下，我们要求第m行的第n个数及之前数的前缀和sum，sum = (m - 1)行的前缀和 + (1 + n) * n / 2;

sum由两部分组成，第一部分是求每一行自身及之前的前缀和，第二部分是简单的求和公式。

目标明确，我们只需要创建两个一维数组map[] 和index[]，分别存储每一行及之前的前缀和，每一行及之前有几个数。

但关键在于如何找到m和n。

例如我们要找第8个数在第几行，我们可以对index[] 数组进行二分查找，第8个数，必然介于第6个数和第10个数之间，所以确定为第4行，那我们的m就是4，第四行前面有index[3]个数，也就是6个数，那么n = 8 - index[m - 1] = 8 - 6 = 2。

到这里我们就分析完毕，剩下开始写代码

数据量为10^12，乘2再开根算得要创建的数组大小为1414214，那我们取个整，1414220.

Code

import java.util.Scanner;

public class Main {
    static long[] map = new long[1414220];
    static long[] index = new long[1414220];

    public static void main(String[] args) {
        init();
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        for (int i = 0; i < T; i++) {
            long a = scan.nextLong(), b = scan.nextLong();
            System.out.println(getSum(b) - getSum(a - 1));
        }
    }

    //初始化操作
    static void init() {
        for (int i = 1; i < map.length; i++) {
            index[i] = index[i - 1] + i;    //在上一行的基础上加i
            map[i] = map[i - 1] + sum(i);    //在上一行的前缀和上加本行的和
        }
    }

    //获取前缀和
    static long getSum(long tar) {
        if (tar == 0) return 0L;
        int m = binarySearch(tar);
        long n = tar - index[m - 1];
        return map[m - 1] + sum(n);
    }

    //二分查找
    static int binarySearch(long tar) {
        int l = 0, r = 1414219, mid;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (index[mid] > tar)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;//找到在第几行
    }

    //求和公式
    static long sum(long x) {
        return (1 + x) * x / 2;
    }
}

试题G: 和与乘积(20分)

分析

不会，咱也不是啥天赋型选手，只能暴力骗点分了…

Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scan.nextInt();
        }
        int count = 0, sum, ji;
        for (int i = 0; i < n; i++) {
            ji = 1;
            sum = 0;
            for (int j = i; j < n; j++) {
                ji *= a[j];
                sum += a[j];
                if (sum == ji)
                    count++;
            }
        }
        System.out.println(count);
    }
}

试题H: 巧克力(20分)

分析

贪心
在保质期允许且数量足够的情况下，优先吃最便宜的，同时沿着保质期的时间，逆向吃（到保质期那天刚好吃完）。为了避免一天吃好多块，我们创建一个boolean数组isTodayEat，用来记录每天是否已经吃过了。

样例输出的18就是这么来滴

1	2	3	4	5	6	7	8	9	10
					1
				1	1
			1	1	1
		1	1	1	1
	1	1	1	1	1
	1	1	1	1	1	2
2	1	1	1	1	1	2
2	1	1	1	1	1	2	3
2	1	1	1	1	1	2	3	3
2	1	1	1	1	1	2	3	3	3

Code

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int date = scan.nextInt();
        int kind = scan.nextInt();
        //记录一下每天吃没吃过巧克力
        boolean[] isTodayEat = new boolean[date + 1];
        //记录一下够吃几天
        int day = 0;
        //记录一下开销
        int money = 0;
        int[][] chocolates = new int[kind + 10][3];
        for (int i = 0; i < kind; i++) {
            //分别表示价格，保质期，数量
            chocolates[i][0] = scan.nextInt();
            chocolates[i][1] = scan.nextInt();
            chocolates[i][2] = scan.nextInt();
        }
        //按照价格升序排序
        Arrays.sort(chocolates, (o1, o2) -> o1[0] - o2[0]);
        for (int[] c : chocolates) {
            //没过保质期，且还有剩余个数
            while (c[1] > 0 && c[2] > 0) {
                //如果今天没吃过的话
                if (!isTodayEat[c[1]]) {
                    isTodayEat[c[1]] = true;
                    //吃了当然就少了一块
                    c[2]--;
                    //拒绝吃白食
                    money += c[0];
                    //记录一下吃够了几天
                    day++;
                }
                //不管你吃没吃，保质期肯定要减一天的
                c[1]--;
            }
        }
        //如果吃够了的天数，等于规定的天数，就输出具体花了多少，没吃够的话就输出-1
        System.out.println(day == date ? money : -1);
    }
}