题解：P8727 [蓝桥杯 2020 国 A] 填空问题

Problem A.

计算从 $1$ 到 $2020$ 中合数的个数。

合数是指除了 $1$ 和它本身外还有其他约数的数（大于 $1$ 的非质数）。

考虑遍历每个数（$2$ 到 $2020$），检查是否存在除 $1$ 和自身外的约数（只需检查到平方根即可）。

答案为 $1713$。

Problem B.

计算从 $1900$ 年 $1$ 月 $1$ 日到 $9999$ 年 $12$ 月 $31$ 日中，年月日的数字表示中包含数字 $2$ 的天数。

考虑遍历每一天，分别检查年、月、日的数字中是否含有 $2$。这里要注意闰年的判断（能被 $4$ 整除但不能被 $100$ 整除，或能被 $400$ 整除）。使用数组存储每月的天数（区分闰年）然后判断即可（这里可以用 to_string() 函数转成字符串进行判断）。

答案是 $1994240$。

Problem C.

给定一个长度为 $200$ 的字符串 $s$，求本质不同的单调递增子序列个数（相同字符序列视为本质相同）。

考虑定义 $dp_i$ 表示以第 $i$ 个字符结尾的本质不同的递增子序列个数。

  • 遍历 $j$ 从 $0$ 到 $i-1$：
    • 若 $s_i = s_j$，则 $dp_i = 0$。
    • 若 $s_i > s_j$，则 $dp_i = dp_i + dp_j$。

最终答案为所有 $dp_i$ 的和。

答案即 $3616159$。

Problem D.

计算 $12$ 阶皮亚诺曲线中所有相邻格子（上下左右）在曲线上的距离之和。

我们设 $f(k)$ 为 $k$ 阶曲线的距离和。
则 $f(k) = 9 \times f(k-1) + \text{水平边界距离和} + \text{垂直边界距离和}$。

边界距离计算使用递归函数计算每个格子在曲线上的坐标。然后对边界上的相邻点计算距离差并求和。

答案：$184731576397539360$。

Problem E.

在 $4 \times 4$ 方格中放置 $16$ 节的玩具蛇（每节占一格，相邻节成直线或直角），求不同放置方案数。

考虑深搜枚举蛇的起点，从起点出发，向四个方向扩展，检查新位置是否在方格内且未被占用。

答案 $552$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "1713", // 双引号中替换为 A 题的答案
        "1994240", // 双引号中替换为 B 题的答案
        "3616159", // 双引号中替换为 C 题的答案
        "184731576397539360", // 双引号中替换为 D 题的答案
        "552", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}