第十一届蓝桥杯 2020年国赛真题 Java 大学B组
所有答案均为个人想法 仅供参考，如有问题 欢迎指正
A 美丽的 2
问题描述小蓝特别喜欢 2，今年是公元 2020年，他特别高兴。 他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中包含数字 2？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
个人答案：
563
public class Main {
public static void main(String[] args) {
int year=1;
int res=0;
while(year<=2020){
if(check(year)) res++;
year++;
}
System.out.println(res);
}
private static boolean check(int year) {
while(year>0){
if(year%10==2) return true;
year = year/10;
}
return false;
}
}B 扩散
问题描述
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点：(0 , 0)，(2020, 11)，(11, 14)，(2000, 2000)。只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。
请问，经过 2020分钟后，画布上有多少个格子是黑色的。答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
个人答案：
20312088
个人代码：
public class Main {
public static void main(String[] args) {
int res=0;
//四个坐标为：(0 , 0)，(2020, 11)，(11, 14)，(2000, 2000)
//根据扩散的规律可以知道扩散的地方横纵坐标和距离中心点的距离只要等于2020就可以
//利用暴力循环判断每个点符合符合规则
for (int x = -2020; x <= 4040; ++x) {
for (int y=-2020;y<=4020;++y){
if (Math.abs(x-0)+Math.abs(y-0)<=2020||
Math.abs(x-2020)+Math.abs(y-11)<=2020||
Math.abs(x-11)+Math.abs(y-14)<=2020||
Math.abs(x-2000)+Math.abs(y-2000)<=2020) res++;
}
}
System.out.println(res);
}
}C 阶乘约数
问题描述
定义阶乘 n ! = 1 × 2 × 3 × ⋅ ⋅ ⋅ × n 。
请问 100! （100 的阶乘）有多少个约数。答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
个人答案：
39001250856960000
个人代码：
public class Main {
public static void main(String[] args) {
//先求出100以内的质数
//10以内的质因数是1 2 3 5 7不用再求了
// String s = "";
// for (int i = 11; i <= 100; ++i) {
// if (check(i)) s += i + ",";
// }
// System.out.println(s);
//100以内的质数为：1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
int[] arr = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int[] count = new int[arr.length];
for (int i = 1; i <= 100; ++i) {
for (int j = 0; j < arr.length; ++j) {
int k = i;
while (k % arr[j] == 0) {
count[j]++;
k = k / arr[j];
}
}
}
long res = 1L;
for (int i = 0; i < count.length; ++i) {
res *= (count[i] + 1);
}
System.out.println(res);
}
//检查某个数 是不是质数
private static boolean check(int i) {
for (int j = 2; j * j <= i; ++j) {
if (i % j == 0) return false;
}
return true;
}
}D 本质上升序列
问题描述
小蓝特别喜欢单调递增的事物。
在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串 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，内容与下面的文本相同）
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl个人答案：
3616159
个人代码（两种方法）：
方法一：动态规划
//秒出结果
public class Main {
static HashSet<String> set = new HashSet<>();
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(new FileInputStream("D:\\inc.txt"));
String s = sc.nextLine();
ArrayList<Character> list = new ArrayList<>();
char[] c = s.toCharArray();
int[] count = new int[c.length];
Arrays.fill(count, 1);
for (int i = 1; i < c.length; ++i) {
for (int j = 0; j < i; ++j) {
if (c[i] == c[j]) count[i] = 0;
if (c[i] > c[j]) count[i] += count[j];
}
}
int res = 0;
for (int i : count) res += i;
System.out.println(res);
}
}方法二：深度优先搜素（DFS）
//大概运行了1min，才算出结果
public class Main {
static HashSet<String> set = new HashSet<>();
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(new FileInputStream("D:\\inc.txt"));
String s = sc.nextLine();
char[] c1 = s.toCharArray();
StringBuilder sb = new StringBuilder();
dfs(c1, 0, sb);
System.out.println(set.size() - 1);
}
public static void dfs(char[] c, int n, StringBuilder sb) {
if (!set.contains(sb.toString())) set.add(sb.toString());
for (int i = n; i < c.length; i++) {
if (sb.length() == 0 || c[i] > sb.charAt(sb.length() - 1)) {
sb.append(c[i]);
dfs(c, i + 1, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}E 玩具蛇
问题描述
小蓝有一条玩具蛇，一共有 16节，上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 A 到 P 共 16个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。
下图给出了两种方案：
请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩
具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
个人答案：
552
代码：
//深度优先搜索，类似于图的遍历
public class Main {
static int[][] diagram = new int[4][4];
static int[][] step = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static int count = 0;
public static void main(String[] args) {
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
diagram = new int[4][4];
diagram[i][j] = 1;
dfs(2, i, j);
}
}
System.out.println(count);
}
public static void dfs(int n, int x, int y) {
if (n > 16) {
count++;
return;
}
for (int i = 0; i < step.length; ++i) {
int curX = x + step[i][0];
int curY = y + step[i][1];
if (check(curX, curY)) {
diagram[curX][curY] = n;
dfs(n + 1, curX, curY);
diagram[curX][curY] = 0;
}
}
}
private static boolean check(int x, int y) {
if (x < 0 || x >= diagram.length || y < 0 || y >= diagram[0].length || diagram[x][y] != 0) return false;
return true;
}
}F 蓝肽子序列
问题描述
L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。 生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。 具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。输入格式
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
输出格式
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
测试样例：
Input：
LanQiaoBei
LanTaiXiaoQiao
Output：
2
Explanation：
最长的公共蓝肽子序列为 LanQiao，共两个蓝肽。评测用例规模与约定
对于 20% 的评测用例，两个字符串的长度均不超过 20。
对于 50% 的评测用例，两个字符串的长度均不超过 100。
对于所有评测用例，两个字符串的长度均不超过 1000。
个人代码：
//最长公共子序列问题（LCS）
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.nextLine();
String s2 = sc.nextLine();
String ss = "";
ArrayList<String> list1 = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
for (int i = 0; i < s1.length(); ++i) {
if ((s1.charAt(i) >= 65 && s1.charAt(i) <= 90 && i != 0)) {
list1.add(ss);
ss = s1.charAt(i) + "";
} else ss += s1.charAt(i);
}
list1.add(ss);
ss = "";
for (int i = 0; i < s2.length(); ++i) {
if ((s2.charAt(i) >= 65 && s2.charAt(i) <= 90 && i != 0)) {
list2.add(ss);
ss = s2.charAt(i) + "";
} else ss += s2.charAt(i);
}
list2.add(ss);
int[][] dp = new int[list1.size() + 1][list2.size() + 1];
for (int i = 0; i < list1.size(); ++i) {
for (int j = 0; j < list2.size(); ++j) {
if (list1.get(i).equals(list2.get(j))) dp[i + 1][j + 1] = dp[i][j] + 1;
else dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
}
}
System.out.println(dp[list1.size()][list2.size()]);
sc.close();
}
}
G 皮亚诺曲线距离
问题描述
皮亚诺曲线是一条平面内的曲线。 下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3 × 3的方格中的每一个格子，最终到达右上角的一条曲线。
下图给出了皮亚诺曲线的 2阶情形，它是经过一个 3^2 × 3^2 的方格中的每一个格子的一条曲线。它是将 1阶曲线的每个方格由 1 阶曲线替换而成。
下图给出了皮亚诺曲线的 3阶情形，它是经过一个3^3 x 3^3的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1阶曲线替换而成。
皮亚诺曲线总是从左下角开始出发，最终到达右上角。
我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是
(0, 0)，右上角坐标是 (3^k-1, 3^k-1),右下角坐标是 (3^k-1 , 0)， 左上角坐标是 (0, 3^k-1)
给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮亚诺曲线走，距离是到少？输入格式
输入的第一行包含一个正整数 k，皮亚诺曲线的阶数。 第二行包含两个整数x1,y1 表示第一个点的坐标。 第三行包含两个整数 x2,y2
表示第二个点的坐标。输出格式
输出一个整数，表示给定的两个点之间的距离。
测试样例1
Input：
1
0 0
2 2
Output：
8测试样例2
Input：
2
0 2
0 3
Output：
13评测用例规模与约定
对于 30% 的评测用例，0 ≤ k ≤ 10。
对于 50% 的评测用例，0 ≤ k ≤ 20。
对于所有评测用例，0 ≤ k ≤ 100 , 0 ≤ x 1 , y 1 , x 2 , y 2 < 3^k , x 1 , y 1 , x 2 , y 2 ≤ 10^18
数据保证答案不超过10^18。
个人思路：
找规律的题，不管k为多少都把所组成的整体分成9个区域。
1.判断（x,y）位于哪个区域，将该区域做为一个整体。
2.计算从起点到该区域，经过的 区域数目*区域面积
3.将（x,y）所在的区域，继续再分成9个小区域，k-1
4.重复1~3，直到k==0 这时候只有一个点了 直接返回1
需要注意：在求 经过的区域数目的时候，进入的入口不一样，经过的路径就不一样，一共有四种进入的入口：
在九个区域中，每个区域进入的方式（和上图颜色对应）：
九个区域，颜色一样的进入的入口就一样，颜色不一样的进入的入口就不一样。
个人代码：
//类似找规律的。
//只能过50%的测试用例，当k=100时，long就会越界。
//可以用BigInteger，我就不改了。
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
long x1 = sc.nextLong();
long y1 = sc.nextLong();
long x2 = sc.nextLong();
long y2 = sc.nextLong();
sc.close();
long dfs1 = dfs(k, x1 + 1, y1 + 1);
long dfs2 = dfs(k, x2 + 1, y2 + 1);
System.out.println(Math.abs(dfs1 - dfs2));
}
public static long dfs(int k, long x, long y) {
if (k == 0) return 1;
long len = (long) Math.pow(3, k - 1);
long i = check(len, x);
long j = check(len, y);
long res = (i - 1) * len * len * 3;
if (i == 2) res += (len * len * (3 - j));
else res += len * len * (j - 1);
if (j == 2 && i == 2) return res + len * len - dfs(k - 1, x - (i - 1) * len, y - (j - 1) * len) + 1;
if (j == 2 && i != 2) {
long x1 =x - (i - 1) * len ;
if (x1 <= len / 3) x1 = len / 3 * 2 + (len / 3 + 1 - x1);
else if (x1 > len / 3 * 2) x1 =(len / 3 + 1) - (x1 - len / 3 * 2);
else x1 = len / 3 * 2 + 1 - (x1 - len / 3);
return res + dfs(k - 1, x1, y - (j - 1) * len) ;
}
if (j != 2 && i == 2) {
long y1 = y - (j - 1) * len;
if (y1 <= len / 3) y1 = len / 3 * 2 + (len / 3 + 1 - y1);
else if (y1 > len / 3 * 2) y1 = (len / 3 + 1) - (y1 - len / 3 * 2);
else y1 = len / 3 * 2 + 1 - (y1 - len / 3);
return res + dfs(k - 1, x - (i - 1) * len, y1);
}
return res + dfs(k - 1, x - (i - 1) * len, y - (j - 1) * len);
}
private static int check(long len, long x) {
if (x > len * 2) return 3;
if (x > len) return 2;
else return 1;
}
}
H 画廊
问题描述
小蓝办了一个画展，在一个画廊左右两边陈列了他自己的作品。为了使画展更有意思，小蓝没有等距陈列自己的作品，而是按照更有艺术感的方式陈列。
在画廊的左边陈列了 L 幅作品，在画廊的右边陈列了 R 幅作品，左边的作品距离画廊的起点依次为 u1, u2, · · · , uL，右边的作品距离画廊起点依次为 v1, v2, · · · , vR。
每周，小蓝要整理一遍自己的每一幅作品。整理一幅作品的时间是固定的，但是要带着沉重的工具。从一幅作品到另一幅作品之间的距离为直线段的长度。
小蓝从画廊的起点的正中央（左右两边的中点）出发，整理好每一幅画，最终到达画廊的终点的正中央。已知画廊的宽为 w。
请问小蓝最少带着工具走多长的距离？输入格式
输入的第一行包含四个整数 L , R , d , w 表示画廊左边和右边的作品数量，
以及画廊的长度和宽度。
第二行包含 L个正整数 u1, u2, · · · , uL，表示画廊左边的作品的位置。
第三行包含 R个正整数 v1, v2, · · · , vR，表示画廊右边的作品的位置。
输出格式
输出一个实数，四舍五入保留两位小数，表示小蓝最少带着工具走的距离。
测试样例
Input：
3 3 10 2
1 3 8
2 4 6
Output：
14.71
Explanation：
小蓝从起点开始，首先到达左边第一幅作品（走动距离 √2），然后到达左边第二幅作品（走动距离 2），
然后到达右边第一幅作品（走动距离 √5），然后到达右边第二幅和第三幅作品（走动距离 2 和 2），
然后到达左边第三幅作品（走动距离 2√2），最后到达画廊终点（走动距离 √5）。
总共距离为 √2 + 2 + √5 + 2 + 2 + 2 √2 + √5 ≈ 14.71。
I 补给
问题描述
小蓝是一个直升飞机驾驶员，他负责给山区的 n nn 个村庄运送物资。每个月，他都要到每个村庄至少一次，可以多于一次，将村庄需要的物资运送过去。每个村庄都正好有一个直升机场，每两个村庄之间的路程都正好是村庄之间的直线距离。
由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过 D DD。每个直升机场都有加油站，可以给直升机加满油。
每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果方便，小蓝中途也可以经过总部来加油。
总部位于编号为 1 11 的村庄。
请问，要完成一个月的任务，小蓝至少要飞行多长距离？
测试样例1
Input：
4 10
1 1
5 5
1 5
5 1
Output：
16.00
Explanation：
四个村庄形成一个正方形的形状。测试样例2
Input：
4 6
1 1
4 5
8 5
11 1
Output：
28.00
Explanation：
补给顺序为 1 → 2 → 3 → 4 → 3 → 2 → 1。评测用例规模与约定
对于所有评测用例，1 ≤ n ≤ 20 , 1 ≤ x i , y i ≤ 10^4 , 1 ≤ D ≤ 10^5。
J 质数行者
测试样例1
Input：
5 6 1
3 4 1 1 2 1
Output：
11
Explanation：
用 (r, c, h) 表示第 r 行第 c 列第 h 层，可能的走法有以下几种：
1. (1, 1, 1) − (1, 3, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
2. (1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
3. (1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
4. (1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
5. (1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
6. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 3, 1) − (5, 6, 1)。
7. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 4, 1) − (5, 6, 1)。
8. (1, 1, 1) − (1, 4, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
9. (1, 1, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
10. (1, 1, 1) − (3, 1, 1) − (3, 6, 1) − (5, 6, 1)。
11. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 6, 1)。
