每日省赛真题解析·第二天
每日省赛真题解析·第二天

每日省赛真题解析·第二天

目录

  • 2021省赛试题D
  • 2021省赛试题E
  • 2021省赛试题F
  • 2021省赛试题G

一.2021省赛试题D

题目链接:货物摆放 – 蓝桥云课 (lanqiao.cn)

题目要求:

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

小蓝有一个超大的仓库,可以摆放很多货物。现在,小蓝有 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(注意有 1616 位数字)时,总共有多少种方案?

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

解题思路:

首先明确(a,b,c) ​肯定是 n ​的因子(n=a×bc​ && n=b×ac​ && n=c×ab)。于是可以筛出n的因子,存入数组中。我们得到 n 的因子数为 128,数目很小,所以可以直接枚举 a,b,c来判断总共的组合数。另外需要注意的是,这道题是要把长宽高分别为1的情况考虑进去的。

最终答案:2430。

代码:


public class Main {
    private static final int maxn = 1010;
    private static long[] a = new long[maxn];

    public static void main(String[] args) {
        long n = 2021041820210418L;
        int len = 0;
        for (long i = 1; i * i <= n; i++) {  //注意等号
            if (n % i == 0) {
                a[len++] = i;
                if (i != n / i) {
                    a[len++] = n / i;
                }
            }
        }
        long cnt = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (a[i] * a[j] > n) {  //注意没有等号
                    continue;
                }
                for (int k = 0; k < len; k++) {
                    if (a[i] * a[j] * a[k] == n) {
                        cnt++;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

二.2021省赛试题E

题目链接:路径 – 蓝桥云课 (lanqiao.cn)

题目要求:

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

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

小蓝的图由 2021 个结点组成,依次编号 1 至 2021。对于两个不同的结点 a, b,如果 a 和 b 的差的绝对值大于 21,则两个结点 之间没有边相连;如果 a 和 b 的差的绝对值小于等于 21,则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

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

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

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

解题思路:

这题建图方式告诉你了,老老实实按照题目说的方式建图,然后单源最短路 dijkstra 算法一下子就跑出来了。

由于蓝桥杯是闭卷,也就是不让带参考材料,很多人记不住 dijkstra 算法,或者比赛的时候一紧张写错了,导致跑出来的答案差了那么一丢丢,就很尴尬了。考虑这道题是填空题,那么不需要在规定时间内完成,那么简单好记的粗暴算法 Floyd 就纳入我们的选择。

为什么说 Floyd 算法粗暴,因为他用的是 DP 的思想,复杂度高达 O(n^3) ,优点就是简单好写。这题 n = 2021 ,n^3 约等于 10 ^ 10​​, 假设考场的电脑性能比较差,一秒只能跑 10^8 ,也就是我们最多运行 100 秒, 2 分钟不到就可以跑出最稳妥的答案。

最终答案:10266837。

代码:

public class Main {

    static final int n = 2021;

    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);
    }

    public static void main(String[] args) {
        //邻接矩阵,初始值为0。下标0-2020对应结点编号1-2021。
        int[][] floyd = new int[n][n];
        //按照题目要求的方式建图。
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n && j < i + 22; j++)
                floyd[i][j] = floyd[j][i] = lcm(i + 1, j + 1);
        //Floyd算法,直接使用floyd[][]作为距离矩阵。
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (floyd[i][k] != 0 && floyd[k][j] != 0 && (floyd[i][j] == 0 || floyd[i][k] + floyd[k][j] < floyd[i][j]))
                        floyd[i][j] = floyd[i][k] + floyd[k][j];
        //输出答案,注意下标和结点编号的对应关系。
        System.out.println(floyd[0][n - 1]);
    }
}

三.2021省赛试题F

题目链接:时间显示 – 蓝桥云课 (lanqiao.cn)

题目要求:

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

解题思路:

简单模拟题。送分题、签到题。

由于不用考虑毫秒,所以可以去掉毫秒的精度。

由于不用考虑年月日,所以只保留最后一天的时间即可。

值得注意的是 1s = 1000ms。

时间复杂度为 O(1)。

代码:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long n = cin.nextLong();
        n /= 1000;
        n %= (24 * 60 * 60);
        System.out.printf("%02d:", n / 3600);
        System.out.printf("%02d:", n / 60 % 60);
        System.out.printf("%02d\n", n % 60);
        cin.close();
    }
}

四.2021省赛试题G

题目链接:最少砝码 – 蓝桥云课 (lanqiao.cn)

题目要求:

你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意 小于等于 N 的正整数重量。那么这套砝码最少需要包含多少个砝码?注意砝码可以放在天平两边。

解题思路:

这个题的样例说明可以说是非常非常的坑人的。如果大家知道可以用进制的方法来解决这道题的话,这道题就是个秒杀题了。详细的介绍可以参考一下下面的这篇博文。三进制与一道经典的砝码问题

代码:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long x=sc.nextLong();
        long sum=1,cur=1;
        while(sum<x){
            sum+=Math.pow(3, cur);
            cur++;
        }
        System.out.println(cur);
    }
}