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

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

目录

  • 2020省赛试题A
  • 2020省赛试题B
  • 2020省赛试题C
  • 2020省赛试题D

一.2020省赛试题A

题目链接:门牌制作 – 蓝桥云课 (lanqiao.cn)

题目要求:

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

小蓝要为一条街的住户制作门牌号。这条街一共有 2020 位住户,门牌号从 1 到 2020 编号。小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符,最后根据需要将字符粘贴到门牌上,例如门牌 1017 需要依次粘贴字符 1、0、1、7,即需要 1 个字符 0,2 个字符 1,1 个字符 7。请问要制作所有的 1 到 2020 号门牌,总共需要多少个字符 2?

解题思路:

一道非常简单的模拟题。

  • 枚举数字 1∼2020​​,把每个数按十进制分解,再统计 2​ 出现的次数即可。
  • 也可以将每个数字都转换为字符串,然后直接统计这些字符串总共有多少个字符 2​。

最终答案:624。

代码:

public class Main {
    public static void main(String[] args) {
        int ans = 0;
        for(int i = 1 ; i <= 2020 ; i ++) {
            int x = i;
            while(x != 0) {
                if(x % 10 == 2) {
                    ans ++;
                }
                x /= 10;
            }
        }
        System.out.println(ans);
    }
}

二.2020省赛试题B

题目链接:寻找 2020 – 蓝桥云课 (lanqiao.cn)

题目要求:

见图片。2020.txt文件在下方网盘链接。

链接:https://pan.baidu.com/s/1GQv_QUM3u32b2aiDxGhnaQ
提取码:eu2v

解题思路:

还是一道非常简单的模拟题。

  1. 将小蓝的矩阵复制到文本文件中以确定矩阵的行数和列数(也可以采用别的方式)。
  2. 以字符串形式逐行读入小蓝的数字矩阵。
  3. 从第一行第一列的位置开始枚举每个位置。
  4. 对于当前位置,分别判断往右走三步、往下走三步、往右下走三步(注意不要越界)所匹配到的字符是否可以和当前位置的字符构成 2020 ,若可以则对答案的贡献加一。

最终答案:16520。

代码:

import java.util.*;
public class Main {

    public static int ans;
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        String[] s = new String[310];
        for(int i = 1 ; i <= 300 ; i ++) {
            s[i] = cin.nextLine();
        }
        for(int i = 1 ; i < s.length; i ++) {
            for(int j = 0 ; j < s[i].length() ; j ++) {
                if(s[i].charAt(j) == '2') {
                    if(j + 3 < s[i].length() && s[i].charAt(j + 1) == '0' && s[i].charAt(j + 2) == '2' && s[i].charAt(j + 3) == '0') ans ++ ;
                    if(i + 3 < s.length && s[i + 1].charAt(j) == '0' && s[i + 2].charAt(j) == '2' && s[i + 3].charAt(j) == '0') ans ++ ;
                    if(j + 3 < s[i].length() && i + 3 < s.length && s[i + 1].charAt(j + 1) == '0' && s[i + 2].charAt(j + 2) == '2' && s[i + 3].charAt(j + 3) == '0') ans ++;
                }
            }
        }
        System.out.println(ans);
        cin.close();
    }
}

三.2020省赛试题C

题目链接:蛇形填数 – 蓝桥云课 (lanqiao.cn)

题目要求:

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

如下图所示,小明用从 11 开始的正整数“蛇形”填充无限大的矩阵。

1 2 6 7 15 ...
3 5 8 14 ...
4 9 13 ...
10 12 ...
11 ...
...

容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列的数是多少?

解题思路:

最终答案:761。

代码:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int r = 1 , c = 1 , ans = 1;
        while(r != 20 || c != 20){
            if(r == 1){
                if(c % 2 == 1) c ++ ;
                else {
                  r ++ ; c --;
                }
            }
            else if(c == 1){
                if(r % 2 == 0) r ++;
                else {
                  r -- ; c ++ ;
                }
            }
            else if((r + c) % 2 == 1) {
              r ++ ; c -- ;
            }
            else {
              r -- ; c ++ ;
            }
            ans ++ ;
        }
        System.out.println(ans);
    }
}

四.2020省赛试题D

题目链接:七段码 – 蓝桥云课 (lanqiao.cn)

解题思路:

我们可以把每个二极管看成一条边,并把相邻的边相连,那么这样题目就可以转换为:有多少种选边方案,使得选出来的边构成的图只有一个联通快。

于是现在只要枚举选边方案,再判断联通块的个数是否为 1 即可。

  • 枚举选边方案可以采用状压(当然直接 dfs 搜索也行):用二进制 1、0 分别表示二进制位所对应的边是选还是不选,复杂度为 2^7。
  • 求联通块的个数可以采用 bfs(也可以采用并查集等方法):从任意一个选中的边出发将所有能到达的选中的边全部打上标记;若标记覆盖了所有选中的边则联通块只有一个(满足条件),反之不止一个联通块(不满足条件)。

最终答案:80。

因为数码管的边数比较少,可以采用暴力手算的方法来解决。在这里就不过多介绍了,有兴趣的同学可以参考下面的这篇博文。2020年第十一届蓝桥杯省赛B组真题:七段码

代码:

import java.util.*;
public class Main {
    private static int ans;
    private static int[][] g = new int[7][7];
    private static boolean[] vis = new boolean[7];
    private static boolean[] flag = new boolean[7];

    private static void bfs(int x) {
        LinkedList<Integer> que = new LinkedList<Integer>();
        que.offer(x);
        vis[x] = true;
        while (!que.isEmpty()) {
            int u = que.peek();
            que.poll();
            for (int i = 0; i <= 6; i++) {
                if (g[u][i] != 0 && flag[i] && !vis[i]) {
                    vis[i] = true;
                    que.offer(i);
                }
            }
        }
    }
    private static boolean check(int x) {
        for (int i = 0; i <= 6; i++) {
            flag[i] = vis[i] = false;
        }
        int cnt = 0;
        for (int i = 6; i >= 0; i--) {
            if ((x >> i & 1) != 0) {
                flag[i] = true;
            }
        }
        for (int i = 0; i <= 6; i++) {
            if (flag[i] && !vis[i]) {
                bfs(i);
                cnt++;
            }
        }
        return cnt == 1;
    }
    public static void main(String[] args) {
        g[0][1] = g[0][5] = 1;
        g[1][0] = g[1][2] = g[1][6] = 1;
        g[2][1] = g[2][3] = g[2][6] = 1;
        g[3][2] = g[3][4] = 1;
        g[4][3] = g[4][5] = g[4][6] = 1;
        g[5][0] = g[5][4] = g[5][6] = 1;
        g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1;
        for (int i = 0; i < (1 << 7); i++) {
            if (check(i)) {
                ans++;
            }
        }
        System.out.print(ans);
        System.out.print('\n');
    }
}