第十一届蓝桥杯大赛软件类决赛
Java大学B组
试题A:美丽的2 （本题总分:5分）
【问题描述】
小蓝特别喜欢2，今年是公元2020年，他特别高兴。他很好奇，在公元1年到公元2020年(包含）中，有多少个年份的数位中包含数字2?
答案：563
解法1.
package exam1;
public class Main {
public static void main(String[] args) {
int sum = 0;
String j;
for (int i = 1; i <= 2020; i++) {
j = i + " ";
if(j.contains("2")) {
sum++;
}
}
System.out.println("sum = " + sum);
}
}
解法2.
package exam1;
public class Main {
public static void main(String[] args) {
int count = 0;
for (int i = 1; i <= 2020; ++i) {
if (2 == i / 1 % 10 || 2 == i / 10 % 10 || 2 == i / 100 % 10 || 2 == i / 1000 % 10) {
++count;
}
}
System.out.println(count);
}
}
试题B:扩散（本题总分:5分）
【问题描述】
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。 小蓝在画布上首先点了以下几个点: (0,0)，(2020,11)，(11,14)，(2000,2000)。只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色(如果原来就是黑色，则还是黑色)。
请问，经过2020分钟后，画布上有多少个格子是黑色的。
package exam1;
class Location{
public int x;
public int y;
public Location(int x,int y) {
this.x = x;
this.y = y;
}
}
package exam1;
import java.util.Arrays;
import java.util.linkedList;
import java.util.Queue;
public class Main {
//设置行走方向 上下左右
public static int[][] direct = {{0,1}, {0,-1}, {-1,0}, {1,0}};
public static void main(String[] args) {
//初始化对象
Location location1 = new Location(0+3000, 0+3000);
Location location2 = new Location(2020+3000, 11+3000);
Location location3 = new Location(11+3000, 14+3000);
Location location4 = new Location(2000+3000, 2000+3000);
//获取一个队列
Queue queue=new linkedList();
queue.add(location1);
queue.add(location2);
queue.add(location3);
queue.add(location4);
//记录是否走
int visited[][]=new int[10010][10010];
//开始BFS(广度优先搜索)
int sum=0;
//来记录分钟
int j=0;
for(int i = 0; i < visited.length; i++){
//将数组visited所有元素赋值0
//public static void fill(int[] a,int val)将指定的 int 值分配给指定 int 型数组的每个元素。
//参数：a - 要填充的数组 val - 要存储在数组所有元素中的值
Arrays.fill(visited[i],0);
}
while(j < 2021) {
//当前队列里有多少点 n
int n = queue.size();
while(n-- > 0){
//移除queue中的第一元素
//poll()获取并移除此队列的头，如果此队列为空，则返回 null。
//返回：队列的头，如果此队列为空，则返回 null
Location curLocation = (Location) queue.poll();
visited[curLocation.x][curLocation.y]=1;
//然后遍历这个位置的四周可以走通的位置,
for(int i = 0; i < direct.length; i++) {
//如果这个位置的四个周围的节点是可以访问,那么加入队列里面
int x = curLocation.x + direct[i][0];
int y = curLocation.y + direct[i][1];
if(visited[x][y] == 1) {
continue;
}
//满足条件 添加到队列里面
//标记当前元素走过
visited[x][y]=1;
//扩散
//boolean add(E e)将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，
//如果当前没有可用的空间，则抛出 IllegalStateException。
queue.add(new Location(x, y));
}
}
j++;
}
for(int i = 0; i <= 10000; i++) {
for(int k = 0; k <= 10000; k++) {
if(visited[i][k] == 1) {
sum++;
}
}
}
System.out.println("sum = " + sum);
}
}
试题C:阶乘约数（本题总分:10分）
【问题描述】
定义阶乘n!=1×2×3×---×n。
请问100! (100的阶乘）有多少个正约数。
package exam1;
import java.util.ArrayList;
public class Main {
public static boolean is_prime(int n) {
if(n == 2) {
return true;
}
//(int)是强制类型转换，也就是把后面Math.ceil(Math.sqrt(n))得到的结果转换成整型。而且是强制取整的方法，不会四舍五入。
//Math.ceil()向上取整，往较大的方向取。
//Math.sqrt(n)就是调对n开方
for(int i = 2; i <= (int)Math.ceil(Math.sqrt(n)); i++) {
if(n % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int arr[] = new int[100+1];
//ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。
//ArrayList 继承了 AbstractList,并实现了 List 接口。
//ArrayList
//E: 泛型数据类型，用于设置 objectName 的数据类型，只能为引用数据类型。objectName: 对象名。
//ArrayList 是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList
for (int j = 2; j < 100; ++j) {
if(is_prime(j)) {
//ArrayList 类提供了很多有用的方法，添加元素到 ArrayList 可以使用 add() 方法:
primes.add(j);
}
}
//数组的toString是把每个数组的元素以，分割的字符串返回的。
//对象的toString返回的是特定的类型[object 类型]。
System.out.println(primes.toString());
for(int k = 2; k <= 100; k++) {
int kk = k;
//"死循环"有两种写法：for(;;)和while(true)，
// 编译前 编译后
// while (1)； mov eax,1
// test eax,eax
// je foo+23h
// jmp foo+18h
// 编译前 编译后
// for (;;)； jmp foo+23h
//对比之下，for(;;)指令少，不占用寄存器，而且没有判断跳转，比while(1)好。
//也就是说两者在在宏观上完全一样的逻辑，但是底层完全不一样，for相对于来说更加简洁明了。
for(;;) {
for(int p:primes) {
if(kk % p == 0) {
++arr[p];
kk = kk / p;
break;
}
}
if(kk == 1)
break;
}
}
long count = 1;
for(int j = 2; j <= 100; ++j) {
if(arr[j] != 0) {
count *= (arr[j] + 1);
}
}
System.out.println(count);
}
}
[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]
39001250856960000
试题D:本质上升序列（本题总分:10分）
【问题描述】
小蓝特别喜欢单调递增的事物。
在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串 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
本质不同的递增子序列有多少个?
package exam4;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
next()不光是在接收键盘输入的内容，而且还是在进行扫描分割。比如next()默认的分隔符是空格。
//nextInt()是取next()然后把字符串解析成一个int数字。它本质是调用了next()方法，
//然后将next()方法返回的字符串再解析成int型数字返回。只是它是把得到的字符串给解析成Int返回，
//而且只能是数字的字符串，即可以解析成数字的字符串才能调用成功，否则会有异常。
String s = sc.next();
//把字符串s转换为一个char类型的数组
//如string s= 'abcde';
// char [] chnum=s.ToCharArray();
//结果 chnum里面保存的是 {'a','b','c','d','e'}
char[] num = s.toCharArray();
dp = new int[s.length()];
//public static void fill(int[] a, int val)将指定的 int 值分配给指定 int 型数组的每个元素。
//参数：a - 要填充的数组 val - 要存储在数组所有元素中的值
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];
}
}
}
System.out.println();
int res=0;
for(int i = 0; i < dp.length; i++) {
res += dp[i];
}
System.out.println(res);
sc.close();
}
}
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
Iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
5977
试题E:玩具蛇（本题总分:15分）
【问题描述】
小蓝有一条玩具蛇，一共有16 节，上面标着数字1至16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成90度角。
小蓝还有一个4×4的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母A到P共16个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。
下图给出了两种方案:
请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
package exam5;
//深度优先遍历就是选一个节点做为起点，先遍历与他相关的一条边，并把起点压入栈中。
//下一步在以遍历的边的另一顶点作为起点，遍历与他相关且没遍历过的边，把顶点其压入栈中。
//依次循环下去。直到一个顶点与其相关的边都遍历过了。这时出栈。遍历出栈顶点相关联的没遍历的边。循环操作。
//（简单就是遍历的顶点加入栈中，直到一个顶点所有边访问了，在出栈，在遍历出栈的顶点的其他边）。
//广度优先遍历就是选一个顶点为起点，先遍历与他相关联的所有顶点，并把它们加入队列中。
//遍历完相关顶点后，出队，在遍历出对顶点相关联的顶点，在把它们入队。
//在出队，循环以上操作。直到队列为空。
//深度优先遍历和广度优先遍历的区别主要在于：
//广度优先遍历是遍历完与一个顶点相关的顶点；
//深度优先遍历每次只遍历一个顶点的一个相关的顶点，循环下去，直到叶子节点，在回溯一个顶点，在遍历其他的顶点。
//1、玩具蛇长度16，就假设是1~16，那1放在不同的格子里面就是不同的情况，所以要暴力枚举起始点1在16个格子里面的情况
//2、在dfs深度搜索里面，我们先列举不存在的情况 if(r<0 || c<0 || r>3 || c>3) (a[r][c]==1)位置已经被占
//3、(number>=15) 当玩具蛇放满的时候，我们就返回1，也就是满足的情况的一种方法。
//4、每一个位置有上下左右四个方向放置蛇sum1 = dfs(r-1,c,a,number+1) //上
// +dfs(r+1,c,a,number+1) //下
// +dfs(r,c-1,a,number+1) //左
// +dfs(r,c+1,a,number+1); //右
//5、a[r][c]=0; //我们尝试走这条路就把它置为1，我们尝试走其他路的时候，就要把刚刚置为1的，重新置为0。
public class Main {
public static int sum = 0; //结果：sum种方法
public static int number = 0; //步数
public static int a[][] = new int[4][4]; //4*4的二维数组
public static int dfs(int r,int c,int a[][],int number) { //r行c列数组a
if (r < 0 || c < 0 || r > 3 || c > 3)
return 0;
if (a[r][c] == 1) //位置已经被占
return 0;
if (number >= 15) //放满玩具蛇
return 1;
a[r][c] = 1; //=1就是被占(尝试走这条路就把它置为1)
int sum1 = 0; //每一个位置有多少种可能性
sum1 = dfs(r-1, c, a, number+1) //上 0,1
+dfs(r+1, c, a, number+1) //下 1,0 1,1 1,2
+dfs(r, c-1, a, number+1) //左 1,1
+dfs(r, c+1, a, number+1); //右
a[r][c] = 0; //尝试走其他路的时候，就要把刚刚置为1的，重新置为0
return sum1;
}
public static void main(String[] args) {
//暴力枚举二维数组所有的位置
for (int i = 0; i <= 3; i++) {
for (int j = 0; j <= 3; j++) {
sum = sum + dfs(i, j, a, 0);
}
}
System.out.println(sum);
}
}
552
试题F:蓝肽子序列（本题总分:15分）【问题描述】
L星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究L星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用1至5个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
package exam6;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
//将相应的字符数组输出相应的字符串数组
public static Object[] get_arr(char[] ch) {
//ArrayList类是一个特殊的数组--动态数组。来自于System.Collections命名空间；
//通过添加和删除元素，就可以动态改变数组的长度。
//添加元素
//方法：1）add(object value);将指定元素object value追加到集合的末尾
// 2） add(int index, Object obj);功能：在集合中指定index位置，添加新元素obj
ArrayList
//String为字符串常量，而StringBuilder和StringBuffer均为字符串变量，
//即String对象一旦创建之后该对象是不可更改的，但后两者的对象是变量，是可以更改的。
StringBuilder sb = new StringBuilder("");
//public StringBuilder append(char[] str)将 char 数组参数的字符串表示形式追加到此序列。
//按顺序将数组参数中的字符追加到此序列中。此字符将增加该参数的长度。
sb.append(ch[0]);
for (int i = 1; i < ch.length; i++) {
if (ch[i] >= 'A' && ch[i] <= 'Z') {
//public boolean add(E e)将指定的元素添加到此列表的尾部。
//public String toString()返回此序列中数据的字符串表示形式。
//将分配一个新的 String 对象，并将它初始化，以包含当前由此对象表示的字符串序列。
//然后返回此 String。对此序列的后续更改不影响该 String 的内容。
list.add(sb.toString());
sb = new StringBuilder("");
}
sb.append(ch[i]);
}
list.add(sb.toString());
//public Object[] toArray()按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。
return list.toArray();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//把字符串s转换为一个char类型的数组
//如string s= 'abcde';
// char [] chnum=s.ToCharArray();
//结果 chnum里面保存的是 {'a','b','c','d','e'}
char c1[] = sc.next().toCharArray();
char c2[] = sc.next().toCharArray();
//java方法中返回一个Object类型的对象表示这个方法返回的类型不受限制，
//因为Object是所有类的父类，返回任意一个类型都属于Object类型。
Object a[] = get_arr(c1);
Object b[] = get_arr(c2);
//标准的动态规划（最长公共子序列，LCS）
int dp[][] = new int[a.length+1][b.length+1];
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
//public boolean equals(Object anObject)将此字符串与指定的对象比较。
//当且仅当该参数不为 null，并且是与此对象表示相同字符序列的 String 对象时，结果才为 true。
if (a[i-1].equals(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[dp.length-1][dp[0].length-1]);
}
}
LanQiaoBei
LanTaiXiaoQiao
2
试题G:皮亚诺曲线距离（本题总分: 20分）
[问题描述]
皮亚诺曲线是--条平面内的曲线。
下图给出了皮亚诺曲线的1阶情形，它是从左下角出发，经过一一个3x3的方格中的每一个格子，最终到达右上角的一条曲线。
下图给出了皮亚诺曲线的2阶情形，它是经过一个32x32的方格中的每--
个格子的一条曲线。它是将1阶曲线的每个方格由1阶曲线替换而成。
下图给出了皮亚诺曲线的3阶情形，它是经过一个33x33的方格中的每--
个格子的一条曲线。它是将2阶曲线的每个方格由1阶曲线替换而成。
皮亚诺曲线总是从左下角开始出发，最终到达右上角。
我们将这些格子放到坐标系中，对于k阶皮亚诺曲线，左下角的坐标是
(0,0)，右上角坐标是(3*-1,3*-1)，右下角坐标是(3k-1,0)， 左上角坐标是
(0,3k- 1)。
给定k阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮
亚诺曲线走，距离是到少?
