蓝桥杯 2021年国赛真题（Java 大学 A 组 ）
考试周末期，找点事做，
更新中。。。
#A 纯质数
本题总分：5 分
问题描述
如果一个正整数只有
1
1
1 和它本身两个约数，则称为一个质数（又称素数）。
前几个质数是：
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
,
31
,
37
,
⋅
⋅
⋅
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · ·
2,3,5,7,11,13,17,19,23,29,31,37,⋅⋅⋅ 。
如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：
2
,
3
,
5
,
7
,
23
,
37
2, 3, 5, 7, 23, 37
2,3,5,7,23,37 都是纯质数，而
11
,
13
,
17
,
19
,
29
,
31
11, 13, 17, 19, 29, 31
11,13,17,19,29,31 不是纯质数。当然
1
,
4
,
35
1, 4, 35
1,4,35 也不是纯质数。
请问，在
1
1
1 到
20210605
20210605
20210605 中，有多少个纯质数？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1903
按序枚举
一种朴素的想法，在打表 [ 1 , 20210605 ] [1,20210605] [1,20210605] 间的质数时，额外的进行一次纯质数效验，并将结果累加起来。
import java.util.ArrayList;
import java.util.List;
public class Test {
public static final int N = 20210605;
public static void main(String[] args) {
boolean[] marked = new boolean[N + 1];
List<Integer> primes = new ArrayList();
marked[0] = marked[1] = true;
int ans = 0;
for (int i = 2; i <= N; i++) {
if (!marked[i]) {
primes.add(i);
boolean flag = false;
for (int k = i; k > 0; k /= 10)
if (flag = marked[k % 10]) break;
if (!flag) ans++;
}
for (int p : primes) {
if (p * i > N) break;
marked[p * i] = true;
if (i % p == 0) break;
}
}
System.out.println(ans);
}
}
按位枚举
在朴素的解法中，我们会发现，很多拆分判断一个质数是否是纯质数是没有必要的，因为在 [ 0 , 10 ) [0,10) [0,10) 中，质数仅占 { 2 , 3 , 5 , 7 } \{2,3,5,7\} {2,3,5,7} 四位，如果仅判断这四个数字组合成的数是否是质数的话，性能能否有进一步的提升呢？
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test {
public static final int N = 20210605;
public static int[][] digits = new int[8][4];
public static void main(String[] args) {
boolean[] primes = new boolean[N + 1];
List<Integer> helper = new ArrayList();
Arrays.fill(primes, 2, N, true);
int ans = 0;
for (int i = 2; i <= N; i++) {
if (primes[i]) helper.add(i);
for (int p : helper) {
if (p * i > N) break;
primes[p * i] = false;
if (i % p == 0) break;
}
}
digits[0] = new int[]{2, 3, 5, 7};
for (int k = 1; k < 7; k++)
for (int i = 0; i < 4; i++)
digits[k][i] = digits[k - 1][i] * 10;
digits[7] = new int[]{ digits[6][0] * 10 };
System.out.println(dfs(primes, 0, 0));
}
public static int dfs(boolean[] primes, int k, int depth) {
if (depth == 8) return k <= N && primes[k] ? 1 : 0;
int ans = primes[k] ? 1 : 0;
for (int a : digits[depth])
ans += dfs(primes, k + a, depth + 1);
return ans;
}
}
实际上性能并没有进一步的提升，并且代码量还有所增加。
这是因为在 ( 1 , N ] (1,N] (1,N] 这个范围中的质数大约有 N ln N \cfrac{N}{\ln N} lnNN 个，而按位组成的可能是纯质数的数大约有 4 ln N 4^{\ln N} 4lnN 个，这显然不是一个增值量级的。
#B 完全日期
本题总分：5 分
问题描述
如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。
例如：
2021
2021
2021 年
6
6
6 月
5
5
5 日的各位数字之和为
2
+
0
+
2
+
1
+
6
+
5
=
16
2 + 0 + 2 + 1 + 6 + 5 = 16
2+0+2+1+6+5=16，而
16
16
16 是一个完全平方数，它是
4
4
4 的平方。所以
2021
2021
2021 年
6
6
6 月
5
5
5 日是一个完全日期。
例如：
2021
2021
2021 年
6
6
6 月
23
23
23 日的各位数字之和为
2
+
0
+
2
+
1
+
6
+
2
+
3
=
16
2 + 0 + 2 + 1 + 6 + 2 + 3 = 16
2+0+2+1+6+2+3=16，是一个完全平方数。所以
2021
2021
2021 年
6
6
6 月
23
23
23 日也是一个完全日期。
请问，从
2001
2001
2001 年
1
1
1 月
1
1
1 日到
2021
2021
2021 年
12
12
12 月
31
31
31 日中，一共有多少个完全日期？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
977
Java党的完全胜利
LocalDate好用。
朴素解法
枚举 [ 2001 [2001 [2001- 01 01 01- 01 01 01， 2021 2021 2021- 12 12 12- 31 ] 31] 31] 这个区间间内的时间，判断然后累加。
import java.time.LocalDate;
public class Test {
public static final int maxPerfect = 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9;
public static final boolean[] perfect = new boolean[maxPerfect + 1];
public static LocalDate start = LocalDate.of(2001, 01, 01);
public static LocalDate end = LocalDate.of(2021, 12, 31);
public static void main(String[] args) {
int count = 0;
for (int i = 1; i * i<= maxPerfect; i++)
perfect[i * i] = true;
while (end.compareTo(start) >= 0) {
if (perfect[calc(start)])
count++;
start = start.plusDays(1);
}
System.out.println(count);
}
public static int calc(LocalDate date) {
String dateStr = date.toString();
int res = 0;
for (int i = dateStr.length() - 1; i >= 0; i--)
if (Character.isDigit(dateStr.charAt(i)))
res += Character.digit(dateStr.charAt(i), 10);
return res;
}
}
朴素改进
在 [ 2001 [2001 [2001- 01 01 01- 01 01 01， 2021 2021 2021- 12 12 12- 31 ] 31] 31] 中，各数位之和不仅存在最大值 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9 = 32 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9 = 32 2+0+1+9+0+9+2+9=32，还存在有最小值 2 + 0 + 0 + 1 + 0 + 1 + 0 + 1 2 + 0 + 0 + 1 + 0 + 1 + 0 + 1 2+0+0+1+0+1+0+1，也就是说，可能的完全平方数，不外乎 3 × 3 3 × 3 3×3、 4 × 4 4 × 4 4×4、 5 × 5 5 × 5 5×5 三个，就这一点我们来简化我们的代码。
import java.time.LocalDate;
public class Test {
public static LocalDate start = LocalDate.of(2001, 01, 01);
public static LocalDate end = LocalDate.of(2021, 12, 31);
public static void main(String[] args) {
int count = 0;
while (end.compareTo(start) >= 0) {
if (isPerfect(start)) count++;
start = start.plusDays(1);
}
System.out.println(count);
}
public static boolean isPerfect(LocalDate date) {
String dateStr = date.toString();
int sum = 0;
for (int i = dateStr.length() - 1; i >= 0; i--)
if (Character.isDigit(dateStr.charAt(i)))
sum += Character.digit(dateStr.charAt(i), 10);
return sum == 3 * 3 || sum == 4 * 4 || sum == 5 * 5;
}
}
不依赖 API 的实现
先统计出平年月份和日期各数位之和的出现次数，然后遍历年份时额外的判断一道是否为闰年。
public class Test {
public static void main(String[] args) {
int[] bigMonth = { 1, 3, 5, 7, 8, 1 + 0, 1 + 2 };
int[] smallMonth = { 4, 6, 9, 1 + 1 };
int[] calendar = new int[9 + 2 + 9 + 1];
int ans = 0;
for (int day = 1; day <= 31; day++)
for (int month : bigMonth)
calendar[month + calc(day)]++;
for (int day = 1; day <= 30; day++)
for (int month : smallMonth)
calendar[month + calc(day)]++;
for (int day = 1; day <= 28; day++)
calendar[2 + calc(day)]++;
for (int year = 2001; year <= 2021; year++) {
if (isLeapYear(year))
if (isLeapYear(year + 2 + 2 + 9)) ans++;
for (int i = 0; i < calendar.length; i++) {
if (calendar[i] == 0) continue;
if (isPerfect(calc(year) + i))
ans += calendar[i];
}
}
System.out.println(ans);
}
public static int calc(int n) {
int res = 0;
do
res += n % 10;
while ((n /= 10) > 0);
return res;
}
public static boolean isPerfect(int num) { return num == 3 * 3 || num == 4 * 4 || num == 5 * 5; }
public static boolean isLeapYear(int year) { return year % 100 == 0 ? year % 400 == 0 : year % 4 == 0; }
}
#C 最小权值
本题总分：10 分
问题描述
对于一棵有根二叉树
T
T
T，小蓝定义这棵树中结点的权值
W
(
T
)
W(T)
W(T) 如下：
空子树的权值为
0
0
0。
如果一个结点
v
v
v 有左子树
L
L
L, 右子树
R
R
R，分别有
C
(
L
)
C(L)
C(L) 和
C
(
R
)
C(R)
C(R) 个结点，则
W
(
v
)
=
1
+
2
W
(
L
)
+
3
W
(
R
)
+
(
C
(
L
)
)
2
C
(
R
)
W(v) = 1 + 2W(L) + 3W(R) + (C(L))^{2} C(R)
W(v)=1+2W(L)+3W(R)+(C(L))2C(R)。
树的权值定义为树的根结点的权值。
小蓝想知道，对于一棵有
2021
2021
2021 个结点的二叉树，树的权值最小可能是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
2653631372
动态规划
根据题意，显然有 N = 2021 N = 2021 N=2021， W ( 0 ) = 0 W(0) = 0 W(0)=0， W ( N ) = min { 1 + 2 W ( L ) + 3 W ( R ) + ( C ( L ) ) 2 C ( R ) } W(N) = \min \{1 + 2W(L) + 3W(R) + (C(L))^{2}C(R)\} W(N)=min{1+2W(L)+3W(R)+(C(L))2C(R)}，其中 L + R = N − 1 L + R = N - 1 L+R=N−1， 0 ≤ L ≤ R ≤ N 0 \leq L \leq R \leq N 0≤L≤R≤N。
状态转移方程就在脸上： d p ( y ) = { 0 i = 0 min { 1 + 2 d p ( l ) + 3 d p ( r ) + l 2 r } l + r = i − 1 ， 0 ≤ l ≤ r ≤ i dp(y)=\left\{ \begin{array}{lr} 0&i = 0\\ \min \{1 + 2dp(l) + 3dp(r) + l^{2}r\}&l + r = i - 1，0 \leq l \leq r \leq i \end{array} \right. dp(y)={0min{1+2dp(l)+3dp(r)+l2r}i=0l+r=i−1，0≤l≤r≤i 也是道签到题。
public class Test {
public static final int N = 2021;
public static void main(String[] args) {
long[] dp = new long[N + 1];
for (int i = 1; i <= N; i++) {
dp[i] = Long.MAX_VALUE;
for (int l = i >> 1; l >= 0; l--)
dp[i] = Math.min(dp[i],
1 + 2 * dp[l] + 3 * dp[i - l - 1] + l * l * (i - l - 1));
}
System.out.println(dp[N]);
}
}
#D 覆盖
本题总分：10 分
问题描述
小蓝有一个国际象棋的棋盘，棋盘的大小为
8
×
8
8 × 8
8×8，即由
8
8
8 行
8
8
8 列共
64
64
64 个方格组成。棋盘上有美丽的图案，因此棋盘旋转后与原来的棋盘不一样。
小蓝有很多相同的纸片，每张纸片正好能覆盖棋盘的两个相邻方格。小蓝想用
32
32
32 张纸片正好将棋盘完全覆盖，每张纸片都覆盖其中的两个方格。
小蓝发现，有很多种方案可以实现这样的覆盖。如果棋盘比较小，方案数相对容易计算，比如当棋盘是
2
×
2
2 × 2
2×2 时有两种方案，当棋盘是
4
×
4
4 × 4
4×4 时有
36
36
36 种方案。但是小蓝算不出他自己的这个
8
×
8
8 × 8
8×8 的棋盘有多少种覆盖方案。
请帮小蓝算出对于这个
8
×
8
8 × 8
8×8 的棋盘总共有多少种覆盖方案。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
2653631372
状压 DP
夜深了，该睡觉了。