刷题日志--随便做做 5.28

蓝桥杯2017省赛：迷宫

链接：https://www.lanqiao.cn/problems/641/learning/

问题叙述

X 星球的一处迷宫游乐场建在某个小山坡上。它是由 10 × 10 相互连通的小房间组成的。

房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：

L 表示走到左边的房间，
R 表示走到右边的房间，
U 表示走到上坡方向的房间，
D 表示走到下坡方向的房间。

X 星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！

开始的时候，直升机把 100100 名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。

迷宫地图如下：

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

请你计算一下，最后，有多少玩家会走出迷宫，而不是在里边兜圈子？

如果你还没明白游戏规则，可以参看下面一个简化的 4x4 迷宫的解说图：

运行限制
最大运行时间：1s
最大运行内存: 128M

分析

没什么技术含量的DFS
由于每个格子已经给出了具体能去的方向，不同于之前的问题（四个方向随便走），所以我们直接DFS就好了，一条道走到黑，如果走到的坐标出界了，那我们就成功走出了迷宫，如果走到了之前走过的格子，那么就只能绕圈圈了，走不出去。

创建一个map数组用来存储我们的迷宫，创建一个vis数组用来记录我们走过的格子，由于这100个人走迷宫是相互独立的，所以vis数组也是相互独立的，我们可以每次都创建一个新的，或者每当一个人走完的时候，就重置一下vis数组，我这里的选择是每次创建一个新的vis数组。

Code

import java.util.*;

public class Main {
    static char[][] map = new char[10][10];
    static boolean[][] vis;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int count = 0;
        //这里用了一个小技巧，可以很方便的录入数据。
        for (int i = 0; i < 10; i++) {
            map[i] = scan.nextLine().toCharArray();
        }
        //两层循环遍历每一个人
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                vis = new boolean[10][10]; //为每个人都创建一个vis数组
                if (dfs(i, j)) count++;
            }
        }
        System.out.println(count);
    }

    private static boolean dfs(int i, int j) {
        //判断是否越界，越界的话就成功走出迷宫，返回true
        if (i > 9 || i < 0 || j > 9 || j < 0) return true;
        //走到了之前走过的格子，那么只能兜圈子，绕不出去了，返回false
        if (vis[i][j]) return false;
        //标记一下这个格子我走过了
        vis[i][j] = true;
        //这里应该没啥好说的
        if (map[i][j] == 'U') return dfs(i - 1, j);
        if (map[i][j] == 'D') return dfs(i + 1, j);
        if (map[i][j] == 'R') return dfs(i, j + 1);
        if (map[i][j] == 'L') return dfs(i, j - 1);
        return false;
    }
}

蓝桥杯2018省赛：星期一

链接：https://www.lanqiao.cn/problems/611/learning/

问题叙述

整个 2020 世纪（19011901 年 11 月 11 日至 20002000 年 1212 月 3131 日之间），一共有多少个星期一？(不要告诉我你不知道今天是星期几)

运行限制
最大运行时间：1s
最大运行内存: 128M

分析

用Java自带的Calendar类，可以很容易的解决日期问题。

关于Calendar类的讲解，在我这篇文章做过详细的叙述。

Java--常用类

https://cyborg2077.github.io/2022/04/15/JavaCommonClasses/

Code

import java.util.Calendar;

public class Main {
    public static void main(String[] args) {
        int res = 0;
        Calendar calendar = Calendar.getInstance();
        calendar.set(1901, Calendar.JANUARY, 1);
        while (calendar.get(Calendar.YEAR) < 2001) {
            if (calendar.get(Calendar.DAY_OF_WEEK) == Calendar.MONDAY) res++;
            calendar.add(Calendar.DAY_OF_YEAR, 1);
        }
        System.out.println(res);
    }
}

蓝桥杯2018省赛：乘积尾零

链接：https://www.lanqiao.cn/problems/612/learning/

问题叙述

如下的 1010 行数据，每行有 1010 个整数，请你求出它们的乘积的末尾有多少个零？

5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211

运行限制
最大运行时间：1s
最大运行内存: 128M

分析

用Java自带的BigInteger算一下，最后输出结果，数一下有31个0

Code

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] nums = new int[100];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = scan.nextInt();
        }
        BigInteger bigInteger = new BigInteger("1");
        for (int i = 0; i < nums.length; i++) {
            bigInteger = bigInteger.multiply(BigInteger.valueOf(nums[i]));
        }
        System.out.println(bigInteger);
    }
}

蓝桥杯2019省赛：平方和

链接：https://www.lanqiao.cn/problems/599/learning/

问题叙述

小明对数位中含有 2、0、1、92、0、1、9 的数字很感兴趣，在 11 到 4040 中这样的数包括 1、2、9、101、2、9、10 至 32、3932、39 和 4040，共 2828 个，他们的和是 574574，平方和是 1436214362。

注意，平方和是指将每个数分别平方后求和。

请问，在 11 到 20192019 中，所有这样的数的平方和是多少？

运行限制
最大运行时间：1s
最大运行内存: 128M

分析

水题一道

Code

public class Main {
    public static void main(String[] args) {
        long sum = 0L;
        for (int i = 1; i <= 2019; i++) {
            if ((i + "").contains("2") || (i + "").contains("0") || (i + "").contains("1") || (i + "").contains("9"))
                sum += i * i;
        }
        System.out.println(sum);
    }
}