【2020年蓝桥杯Java-B组国赛题解】

🍡 A 美丽的2（模拟）

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

答案：563

🍯 B 扩散（BFS多起点搜索）

【问题描述】
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。

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

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

典型的BFS，属于是多起点的BFS题目。注意原来是黑点的就不用再入队，否则会运行超时。

import java.util.*;
import java.io.*;class node {int x, y;node() {}node(int x, int y) {this.x = x;this.y = y;}
}
public class Main {static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static int[] xx = new int[] {0,0,1,-1};static int[] yy = new int[] {1,-1,0,0};public static void main(String[] args) throws IOException {// 为避免出现负数情况，所有值都+2020int x1 = 2020;int y1 = 2020;int x2 = 4040;int y2 = 2020 + 11;int x3 = 2020 + 11;int y3 = 2020 + 14;int x4 = 2020 + 2000;int y4 = 2020 + 2000;int[][] point = new int[7000][7000];Queue<node> queue = new LinkedList<>();queue.offer(new node(x1, y1));queue.offer(new node(x2, y2));queue.offer(new node(x3, y3));queue.offer(new node(x4, y4));// 记录轮数int time = 0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {node cur = queue.poll();for (int j = 0; j < 4; j++) {int tx = cur.x + xx[j];int ty = cur.y + yy[j];// 注意不要重复入队，否则必超时if (point[tx][ty] == 1) continue;point[tx][ty] = 1;queue.offer(new node(tx, ty));}}// 全部完成一轮time++;if (time == 2020) {break;}}int ans = 0;for (int i = 0; i < 7000; i++) {for (int j = 0; j < 7000; j++) {if (point[i][j] == 1) {ans++;}}}System.out.println(ans);}
}

答案：20312088

🍕 C 阶乘约数（不同约数个数问题）

对于数字4，可以拆分成2的2次方，所以4的全部因数（约数）个数 = 1 * 3 = 3（1 2 4三个），这里要注意区别质因数、因数（约数），我们是用到了：一个自然数可以唯一地表示成一些质因数的乘积，这个定理，在此基础上引出了求解自然数N的全部因数（约数）个数的方法。

回到本题，要求100阶乘的正约数，也就是求1-100每个数的正约数个数即可。
上面的定理一定要记牢，遇到求约数问题常常会考！！！

答案：39001250856960000

import java.util.*;
import java.io.*;public class Main {static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {// 记录所有质因数的次数int[] cnt = new int[110];for (int i = 1; i <= 100; i++) {int tmp = i;for (int j = 2; j <= Math.sqrt(tmp); j++) {// 求所有可能质因数while (tmp % j == 0) {cnt[j]++;tmp /= j;}}// 说明i是质数if (tmp != 1) {cnt[tmp]++;}}// 统计所有正约数个数long ans = 1L;for (int i = 1; i <= 100; i++) {ans *= (1 + cnt[i]);}System.out.println(ans);}
}

※🥙 D 本质上升序列（DP）

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

答案：3616159

有点类似于<最长递增子序列>，但又不是求最大长度，而是求种类数，那么肯定需要对dp数组的值进行累加。

dp[i]，表示以字符串中第 i 个元素结尾的子串的本质不同的递增子序列的个数，而每一个子串，无非就是以每个元素结尾的，所以最终我们要求的结果就 = dp[0] + dp[1] + dp[2] + … + dp[n - 1]。

显然，对于单独每个字符，个数都=1。
对于abcd而言，站在c的角度往前考虑，c的前面可以放a、b，c可以直接放在a后面，也可以直接放在b后面（b前面放什么就由b自己来管，c不用管），所以dp[c] += dp[a] dp[c] += dp[b]。这是前面的字符小于后面字符的情况，如果等于呢？

对于abcbd而言，站在第二个b的角度向前考虑，考虑到前面第一个b时，发现 b == b，因为题目要求严格递增，并且要本质不同，所以需要将dp[b2] -= dp[b1]，因为dp[b2]会统计第一个b之前的组合方式，但b1之前已经统计过了，b2再统计就重复了，所以需要减去。
$$\begin{gathered} dp[i]+=dp[j]ifstr[j]<str[i] \\ dp[i]-=dp[j]ifstr[j]=str[i] \\ 0<j<i<length \end{gathered}$$

import java.util.*;
import java.io.*;public class Main {static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {String str = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";char[] chars = str.toCharArray();int n = chars.length;// dp[i] 前i个字符的本质不同的递增子序列有多少个int[] dp = new int[n + 1];// 对于每个单独的字符，值都=1Arrays.fill(dp, 1);for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (chars[j] < chars[i]) {dp[i] += dp[j];}if (chars[j] == chars[i]) {dp[i] -= dp[j];}}}long ans = 0L;for (int i = 0; i < n; i++) {ans += dp[i];}System.out.println(ans);}
}

🥘 E 玩具蛇（DFS多起点）

小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 A 到 P 共 16 个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

DFS搜索，每个点都可以作为起点，注意搜索之后要回溯。
答案：552

import java.util.*;
import java.io.*;public class Main {static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static boolean[][] vis = new boolean[5][5];static int[] x = new int[] {0,0,1,-1};static int[] y = new int[] {1,-1,0,0};static int ans = 0;public static void main(String[] args) throws IOException {// 枚举所有可能起点for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {// 每次从新起点开始遍历都需要重置visvis = new boolean[5][5];vis[i][j] = true;dfs(i, j, 2);}}System.out.println(ans);}static void dfs(int xx, int yy, int next) {if (next == 16 + 1) {ans++;return;}for (int i = 0; i < 4; i++) {int tx = xx + x[i];int ty = yy + y[i];if (tx < 0 || ty < 0 || tx >= 4 || ty >= 4) continue;if (vis[tx][ty]) continue;// 当前位置可以放vis[tx][ty] = true;dfs(tx, ty, next + 1);// 回溯，不放当前位置，注意：固定了起点vis[tx][ty] = false;}}
}

🥞 F 蓝肽子序列（DP：最长公共子序列）

看这道题之前，先看看这道<最长公共子序列>问题：

此题属于编辑距离类题目的典型问题，动态转移方程都类似，不了解的同学可以去这里看看，动态规划专题一

定义dp[i][j]数组含义为：text1[1…i] 与 text2[1…j] 的最长公共子序列的最大长度，所以最终答案 = dp[n1][n2]。

class Solution {public int longestCommonSubsequence(String text1, String text2) {int n1 = text1.length();int n2 = text2.length();// dp[i][j] // text1[1...i] 与 text2[1...j] 的最长公共子序列的长度int[][] dp = new int[n1 + 1][n2 + 1];for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {// 两个字符相等if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相等，取决于删除text1 或 text2中某个字符的最大情况dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[n1][n2];}
}

回到本题，看了上面的代码后，相信大家都有思路了，不就是把dp考虑的最小单位从字符变到了字符串。

import java.util.*;
import java.io.*;public class Main {static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {String a = reader.readLine().trim();String b = reader.readLine().trim();// 提取出每个蓝肽序列中的子序列String[] str_a = new String[1000];String[] str_b = new String[1000];int n1 = a.length();int n2 = b.length();// 找第一个蓝肽序列的子序列int index = 0;for (int i = 0;;) {if (i >= n1) break;char c = a.charAt(i);// 找到了蓝肽的大写字母开头if (c >= 'A' && c <= 'Z') {int j = i + 1;// 找到当前蓝肽的结束位置while (j < n1 && a.charAt(j) >= 'a' && a.charAt(j) <= 'z') {j++;}String sub = a.substring(i, j);str_a[index++] = sub;i += sub.length();}}n1 = index;// 找第二个蓝肽序列的子序列index = 0;for (int i = 0;;) {if (i >= n2) break;char c = b.charAt(i);// 找到了蓝肽的大写字母开头if (c >= 'A' && c <= 'Z') {int j = i + 1;// 找到当前蓝肽的结束位置while (j < n2 && b.charAt(j) >= 'a' && b.charAt(j) <= 'z') {j++;}String sub = b.substring(i, j);str_b[index++] = sub;i += sub.length();}}n2 = index;// dp[i][j], str_a[1...i] 与 str_b[1...j] 的最长公共子序列的长度// 这里考虑的基本单位为：子串，不再是之前题目中的字符int[][] dp = new int[n1 + 1][n2 + 1];for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {// 对应于两个字符相等的情况if (str_a[i - 1].equals(str_b[j - 1])) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不等，取决于两个中的最大值dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}System.out.println(dp[n1][n2]);}
}

喜欢这种自己摸得着的题目，哈哈哈哈哈，好歹知道该怎么进行转换。

🍶 G 皮亚诺曲线

没想到好的解决方案。