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

试题A：美丽的2(5分)

问题描述

小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中包含数字 2？

分析

签到题，没什么好说的

答案：563

Code

public class Main {
    public static void main(String[] args) {
        int sum = 0;
        for (int i = 1; i <= 2020; i++) {
            for (char c : (i + "").toCharArray()) {
                if (c == '2') {
                    sum++;
                    break;
                }
            }
        }
        System.out.println(sum);
    }
}

试题B：扩散(5分)

问题描述

小蓝在一张无限大的特殊画布上作画。

这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。只有这几个格子上有黑色，其它位置都是白色的。每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。

请问，经过 2020 分钟后，画布上有多少个格子是黑色的。

分析

BFS
画布是无限大，(0, 0)这个点会扩散到负坐标，所以我们干脆把所有坐标加上3000，拿一个8000×8000的数组来装
代码跟之前写的二叉树的层序遍历的模板有点像，层序遍历是遍历当层节点时，将该节点的子节点，加入到队列中
这道题可以抽象成一个四叉树，遍历完每个点的时候，将其周围的四个点加入队列中(需要判断一下周围四个点是否已经有黑点了，把不是黑点的添加到队列就行了)。
附上那篇文章的连接

二叉树相关习题

https://cyborg2077.github.io/2022/02/15/BinaryTree

答案：20312088

Code

public class Main {
    static int[][] move = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static boolean[][] isBlack = new boolean[8000][8000];
    static int res = 4;

    public static void main(String[] args) {
        LinkedList<Point> queue = new LinkedList<>();
        queue.add(new Point(3000, 3000, 0));
        queue.add(new Point(5020, 3011, 0));
        queue.add(new Point(3011, 3014, 0));
        queue.add(new Point(5000, 5000, 0));
        isBlack[3000][3000] = true;
        isBlack[5020][3011] = true;
        isBlack[3011][3014] = true;
        isBlack[5000][5000] = true;
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            if (p.time == 2020) break;
            isBlack[p.x][p.y] = true;
            for (int i = 0; i < move.length; i++) {
                int x = p.x + move[i][0];
                int y = p.y + move[i][1];
                if (!isBlack[x][y]) {
                    queue.add(new Point(x, y, p.time + 1));
                    isBlack[x][y] = true;
                    res++;
                }
            }
        }
        System.out.println(res);
    }
}

class Point {
    int x;
    int y;
    int time;

    public Point(int x, int y, int time) {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

试题C：阶乘约数(10分)

问题描述

定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。

分析

100的阶乘，肯定是要用到BigInteger的，主要考察的是算数基本定理，数论里的东西，给定一个数n，求n的因子个数
下面是算数基本定理的模板，我们把它改写成BigInteger的就行

static int factors(long n) {
        int res = 1, now;
        for (int i = 2; i * i <= n; i++) {
            now = 1;
            while (n % i == 0) {
                n /= i;
                now++;
            }
            if (now > 1)
                res *= now;
        }
        return n > 1? res *2 : res;
    }

答案: 39001250856960000

Code

public class Main {
    public static void main(String[] args) {
        BigInteger s = BigInteger.ONE;
        for (int i = 1; i <= 100; i++) {
            s = s.multiply(new BigInteger(i + ""));
        }
        System.out.println(getNum(s));
    }

    static BigInteger getNum(BigInteger s) {
        BigInteger res = BigInteger.valueOf(1), now;
        for (BigInteger i = BigInteger.valueOf(2); i.multiply(i).compareTo(s) <= 0; i = i.add(BigInteger.valueOf(1))) {
            now = BigInteger.valueOf(1);
            while (s.mod(i).compareTo(BigInteger.ZERO) == 0) {
                s = s.divide(i);
                now = now.add(BigInteger.valueOf(1));
            }
            if (now.compareTo(BigInteger.valueOf(1)) > 0)
                res = res.multiply(now);
        }
        return s.compareTo(BigInteger.valueOf(1)) > 0 ? res.multiply(BigInteger.valueOf(2)) : res;
    }
}

试题D：本质上升序列(10分)

问题描述

小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？

例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。

请问对于以下字符串（共 200 个小写英文字母，分四行显示）：（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不同的递增子序列有多少个？

分析

线性DP
dp[i]表示以s[i]结尾的本质不同的上升序列个数，而dp[i]与s[j] (0<j<i-1) 有关
如果s[i] > s[j]，那么dp[i] = dp[i] + dp[j]，这个应该很好理解
dp[j]是以s[j]结尾的上升序列个数，而s[i] > s[j]，那么dp[i]就是自身加上dp[j]

dp[i]是以s[i]结尾的本质不同的递增子序列数量，如果s[i] == s[j]，说明有相同字符结尾的序列，那dp[i]中必然包含了dp[j]中的所有序列，所以要减去dp[j]中重复的序列

举个例子 1 2 7 8 3 7

dp[i]	dp的值	对应的元素
dp[0]	1	1
dp[1]	2	2 12
dp[2]	4	7 17 27 127
dp[3]	8	8 18 28 78 128 178 278 1278
dp[4]	4	13 23 123
dp[5]	4	7 17 27 127 137 127 1237 37

s[2] == s[5] 均为7，可以看出dp[5]中包含了dp[2]中的所有内容，故要减去之后才是正解

Code

import java.util.*;

public class Main {
	public static void main(String[] args) {
		char[] s = ("tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf" +
				"iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij" +
				"gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad" +
				"vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl").toCharArray();
		int[] dp = new int[s.length];
		Arrays.fill(dp, 1);
		for (int i = 0; i < s.length; i++) {
			for (int j = 0; j < i; j++) {
				if (s[i] > s[j]) dp[i] += dp[j];
				if (s[i] == s[j]) dp[i] -= dp[j];
			}
		}
		System.out.println(Arrays.stream(dp).sum());
	}
}

试题E：玩具蛇(15分)

题目：

问题描述

小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 A 到 P 共 16 个字母。小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

下图给出了两种方案：

分析

回溯，依次将每一个格子当初起点。
创建一个used数组，记录每个格子是否用过
创建一个move数组，用来遍历上下左右四个方向
创建一个res变量，用来储存方案数
回溯条件，当前玩具蛇长度为16，同时res++;
答案: 552

Code

public class Main {
    static boolean[][] used = new boolean[5][5];
    static int res = 0;
    static int[][] move = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                used[i][j] = true;
                backTrack(i, j, 1);
                used[i][j] = false;
            }
        }
        System.out.println(res);
    }

    static void backTrack(int x, int y, int length) {
        if (length == 16) {
            res++;
            return;
        }
        for (int i = 0; i < move.length; i++) {
            int x1 = x + move[i][0];
            int y1 = y + move[i][1];
            if (x1 <= 4 && x1 >= 1 && y1 <= 4 && y1 >= 1 && !used[x1][y1]) {
                used[x1][y1] = true;
                backTrack(x1, y1, length + 1);
                used[x1][y1] = false;
            }
        }
    }
}

试题F：蓝肽子序列(15分)

分析

最长公共子序列问题
力扣：https://leetcode.cn/problems/qJnOS7/
只需要将给出的字符串，按照大写字母，拆成一个一个单词，就可以转化为上面的问题。

Code

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String s1 = scan.next();
		ArrayList<String> strs1 = new ArrayList<>();
		int tmp = 0;
		for (int i = 1; i < s1.length(); i++) {
			char c = s1.charAt(i);
			if (c >= 'A' && c <= 'Z') {
				strs1.add(s1.substring(tmp, i));
				tmp = i;
			}
		}
		strs1.add(s1.substring(tmp));
		String s2 = scan.next();
		ArrayList<String> strs2 = new ArrayList<>();
		int tmp2 = 0;
		for (int i = 1; i < s2.length(); i++) {
			char c = s2.charAt(i);
			if (c >= 'A' && c <= 'Z') {
				strs2.add(s2.substring(tmp2, i));
				tmp2 = i;
			}
		}
		strs2.add(s2.substring(tmp2));
		int[][] dp = new int[strs1.size() + 1][strs2.size() + 1];
		for (int i = 1; i <= strs1.size(); i++) {
			for (int j = 1; j <= strs2.size(); j++) {
				if (strs1.get(i - 1).equals(strs2.get(j - 1))) dp[i][j] = 1 + dp[i - 1][j - 1];
				else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		System.out.println(dp[strs1.size()][strs2.size()]);
	}
}