蓝桥杯历年真题及解析.

A: 美丽的 2

题目：

【问题描述】
小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。
他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中
包含数字 2？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析：

枚举暴力check

AC代码：

563

B: 扩散

题目：

【问题描述】
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它
就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色
（如果原来就是黑色，则还是黑色）。
请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析：

定义两个set容器，装状态压缩的坐标，
定义一个二维数组标记中心。

AC代码：

20312088

import java.util.HashSet;

public class B {
	public static HashSet<Integer> set1=new HashSet<Integer>();
	public static HashSet<Integer> set2=new HashSet<Integer>();
	public static boolean center[][]=new boolean[10000][10000];
	public static void in(int n){
		int x=n/10000;
		int y=n%10000;
		center[x][y]=true;
		for(int i=-1;i<2;i++){
			for(int j=-1;j<2;j++){
				if(Math.abs(i+j)==1&&!center[x+i][y+j]){
					set2.add((x+i)*10000+y+j);
				}
			}
		}
	}
	public static void main(String[] args) {
		set1.add(50005000);
		set1.add(70205011);
		set1.add(50115014);
		set1.add(70007000);
		for(int i=0;i<2020;i++){
			for(int x:set1){
				in(x);
			}
			set1.clear();
			set1.addAll(set2);
			set2.clear();
			System.out.println(i);
		}
		for(int n:set1){
			int x=n/10000;
			int y=n%10000;
			center[x][y]=true;
		}
		long ans=0;
		for(int i=0;i<10000;i++){
			for(int j=0;j<10000;j++){
				ans+=center[i][j]?1:0;
			}
		}
		System.err.println(ans);
	}
}

C: 阶乘约数

题目：

【问题描述】
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析：

先用Big Integer求出100！
然后根据约数个数定理求出
100！=Πpi^ai
ans=Π(ai+1)

AC代码：

39001250856960000

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，内容与下面的文本相同）
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析：

AC代码：

import java.util.Arrays;
import java.util.Scanner;

public class D{
    public static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char[] num = s.toCharArray();
        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 (num[j] < num[i]) {
                    dp[i] += dp[j];
                }
                if (num[j] == num[i]) {
                    dp[i] -= dp[j];
                }
            }
        }
        int res=0;
        for (int i = 0; i < dp.length; i++) {
            res+=dp[i];
        }
        System.out.println(res);
    }
}

E: 玩具蛇

题目：

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

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩
具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析：

暴力枚举起点，然后DFS

AC代码：

552

F: 蓝肽子序列

题目：

【问题描述】
L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾
连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，
想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，
后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，
并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子
序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个
子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
【输入格式】
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空
格等分隔字符。
【输出格式】
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
【样例输入】
LanQiaoBei
LanTaiXiaoQiao
【样例输出】
2
【样例说明】
最长的公共蓝肽子序列为 LanQiao，共两个蓝肽。
【评测用例规模与约定】
对于 20% 的评测用例，两个字符串的长度均不超过 20。
对于 50% 的评测用例，两个字符串的长度均不超过 100。
对于所有评测用例，两个字符串的长度均不超过 1000。

分析：

标准动态规划

AC代码：

G: 皮亚诺曲线距离

题目：

【问题描述】
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3 × 3 的
方格中的每一个格子，最终到达右上角的一条曲线。

下图给出了皮亚诺曲线的 2 阶情形，它是经过一个 32 × 32 的方格中的每一
个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

下图给出了皮亚诺曲线的 3 阶情形，它是经过一个 33 × 33 的方格中的每一
个格子的一条曲线。

它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。
皮亚诺曲线总是从左下角开始出发，最终到达右上角。
我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是
(0, 0)，右上角坐标是 (3k k 1, 3k k 1)，右下角坐标是 (3k k 1, 0)，左上角坐标是
(0, 3k k 1)。
给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮
亚诺曲线走，距离是到少？
【输入格式】
输入的第一行包含一个正整数 k，皮亚诺曲线的阶数。
第二行包含两个整数 x1, y1，表示第一个点的坐标。
第三行包含两个整数 x2, y2，表示第二个点的坐标。
【输出格式】
输出一个整数，表示给定的两个点之间的距离。
【样例输入】
1
0 0
2 2
【样例输出】
8
【样例输入】
2
0 2
0 3
【样例输出】
13
【评测用例规模与约定】
对于 30% 的评测用例，0 ≤ k ≤ 10。
对于 50% 的评测用例，0 ≤ k ≤ 20。
对于所有评测用例，0 ≤ k ≤ 100, 0 ≤ x1, y1, x2, y2 < 3k, x1, y1, x2, y2 ≤ 1018。
数据保证答案不超过 1018。

分析：

AC代码：

H: 画廊

题目：

【问题描述】
小蓝办了一个画展，在一个画廊左右两边陈列了他自己的作品。为了使画
展更有意思，小蓝没有等距陈列自己的作品，而是按照更有艺术感的方式陈列。
在画廊的左边陈列了 L 幅作品，在画廊的右边陈列了 R 幅作品，左边的作品距
离画廊的起点依次为 u1, u2, · · · , uL，右边的作品距离画廊起点依次为 v1, v2, · · · , vR。
每周，小蓝要整理一遍自己的每一幅作品。整理一幅作品的时间是固定的，
但是要带着沉重的工具。从一幅作品到另一幅作品之间的距离为直线段的长度。
小蓝从画廊的起点的正中央（左右两边的中点）出发，整理好每一幅画，
最终到达画廊的终点的正中央。已知画廊的宽为 w。
请问小蓝最少带着工具走多长的距离？
【输入格式】
输入的第一行包含四个整数 L, R, d, w，表示画廊左边和右边的作品数量，
以及画廊的长度和宽度。
第二行包含 L 个正整数 u1, u2, · · · , uL，表示画廊左边的作品的位置。
第三行包含 R 个正整数 v1, v2, · · · , vR，表示画廊右边的作品的位置。
【输出格式】
输出一个实数，四舍五入保留两位小数，表示小蓝最少带着工具走的距离。
【样例输入】
3 3 10 2
1 3 8
2 4 6
【样例输出】
14.71
【样例说明】
小蓝从起点开始，首先到达左边第一幅作品（走动距离 √2），然后到达左
边第二幅作品（走动距离 2），然后到达右边第一幅作品（走动距离 √5），然后
到达右边第二幅和第三幅作品（走动距离 2 和 2），然后到达左边第三幅作品
（走动距离 2 √2），最后到达画廊终点（走动距离 √5）。
总共距离为 √
2 + 2 + √
5 + 2 + 2 + 2 √
2 + √5 ≈ 14.71。
【评测用例规模与约定】
对于 40% 的评测用例，1 ≤ L, R ≤ 10, 1 ≤ d ≤ 100, 1 ≤ w ≤ 100。
对于 70% 的评测用例，1 ≤ L, R ≤ 100, 1 ≤ d ≤ 1000, 1 ≤ w ≤ 1000。
对于所有评测用例，1 ≤ L, R ≤ 500, 1 ≤ d ≤ 100000, 1 ≤ w ≤ 100000, 0 ≤ u1 < u2 < · · · < uL ≤ d, 0 ≤ v1 < v2 < · · · < vR ≤ d。

分析：

AC代码：

I: 补给

题目：

【问题描述】
小蓝是一个直升飞机驾驶员，他负责给山区的 n 个村庄运送物资。每个月，
他都要到每个村庄至少一次，可以多于一次，将村庄需要的物资运送过去。每
个村庄都正好有一个直升机场，每两个村庄之间的路程都正好是村庄之间的直
线距离。
由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过 D。每个直升
机场都有加油站，可以给直升机加满油。
每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果
方便，小蓝中途也可以经过总部来加油。
总部位于编号为 1 的村庄。
请问，要完成一个月的任务，小蓝至少要飞行多长距离？
【输入格式】
输入的第一行包含两个整数 n, D，分别表示村庄的数量和单次飞行的距离。
接下来 n 行描述村庄的位置，其中第 i 行两个整数 xi, yi，表示编号为 i 的
村庄的坐标。村庄 i 和村庄 j 之间的距离为 √(xi xj)2 + (yi yj)2。
【输出格式】
输出一行，包含一个实数，四舍五入保留正好 2 位小数，表示答案。
【样例输入】
4 10
1 1
5 5
1 5
5 1
【样例输出】
16.00
【样例说明】
四个村庄形成一个正方形的形状。
【样例输入】
4 6
1 1
4 5
8 5
11 1
【样例输出】
28.00
【样例说明】
补给顺序为 1 → 2 → 3 → 4 → 3 → 2 → 1。
【评测用例规模与约定】
对于所有评测用例，1 ≤ n ≤ 20, 1 ≤ xi, yi ≤ 104, 1 ≤ D ≤ 105。

分析：

AC代码：

J: 质数行者

题目：

【问题描述】
小蓝在玩一个叫质数行者的游戏。
游戏在一个 n × m × w 的立体方格图上进行，从北到南依次标号为第 1 行到
第 n 行，从西到东依次标号为第 1 列到第 m 列，从下到上依次标号为第 1 层到
第 w 层。
小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w
层。每一步，他可以向东走质数格、向南走质数格或者向上走质数格。每走到
一个位置，小蓝的角色要稍作停留。
在游戏中有两个陷阱，分别为第 r1 行第 c1 列第 h1 层和第 r2 行第 c2 列第
h2 层。这两个陷阱的位置可以跨过，但不能停留。也就是说，小蓝不能控制角
色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。
小蓝最近比较清闲，因此他想用不同的走法来完成这个游戏。所谓两个走
法不同，是指小蓝稍作停留的位置集合不同。
请帮小蓝计算一下，他总共有多少种不同的走法。
提示：请注意内存限制，如果你的程序运行时超过内存限制将不得分。
【输入格式】
输入第一行包含两个整数 n, m, w，表示方格图的大小。
第二行包含 6 个整数，r1, c1, h1, r2, c2, h2，表示陷阱的位置。
【输出格式】
输出一行，包含一个整数，表示走法的数量。答案可能非常大，请输出答
案除以 1000000007 的余数。
【样例输入】
5 6 1
3 4 1 1 2 1
【样例输出】
11
【样例说明】
用 (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)。
    【评测用例规模与约定】
    对于 30% 的评测用例 1 ≤ n, m,w ≤ 50。
    对于 60% 的评测用例 1 ≤ n, m,w ≤ 300。
    对于所有评测用例，1 ≤ n, m, w ≤ 1000，1 ≤ r1,r2 ≤ n, 1 ≤ c1, c2 ≤ m, 1 ≤ h1, h2 ≤ w，陷阱不在起点或终点，两个陷阱不同。

分析：

AC代码：