第十届蓝桥杯 JAVA C组 省赛真题_试题 a: 求和 本题总分:5 分 【问题描述】 小明对数位中含有 2、0、1、9 的数

---

一、求和

1.题目详情

试题 A: 求和
本题总分：5 分
【问题描述】
小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包
括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 2019 中，所有这样的数的和是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1
2
3
4
5
6
7
8
9

2.解题代码

方法一：.contains()方法：判断一个字符串中是否存在这个字符
1

package javac_9_19;

public class Test01_2 {
	public static void main(String[] args) {
		int sum = 0;
		for (int i = 0; i <= 2019; i++) {
			// 将数字转换为字符串
//			String str = i+"";
			String str = String.valueOf(i);
			
			if (str.contains("2") || str.contains("0") || str.contains("1") ||str.contains("9")) {
				sum += i;
			}
		}
		System.out.println(sum);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二: 
1

package javac_9_19;

public class Test01 {
	// 答案: 1905111
	public static void main(String[] args) {
		int sum = 0;
		for (int i = 1; i <= 2019; i++) {
			if (f(i)) {
				sum += i;
			}
		}
		System.out.println(sum);
	}
	
	/**
	 * 判断一个数是否包含2,0,1,9
	 * @param x
	 * @return
	 */
	public static boolean f(int x) {
		while (x != 0) {
			if (x % 10 == 0 || x % 10 == 1 || x % 10 == 2 || x % 10 == 9) {
				return true;
			} else {
				x /= 10;
			}
		}
		return false;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

二、矩形切割

1.题目详情

试题 B: 矩形切割
本题总分：5 分
【问题描述】
小明有一些矩形的材料，他要从这些矩形材料中切割出一些正方形。
当他面对一块矩形材料时，他总是从中间切割一刀，切出一块最大的正方
形，剩下一块矩形，然后再切割剩下的矩形材料，直到全部切为正方形为止。
例如，对于一块两边分别为 5 和 3 的材料（记为 5 × 3），小明会依次切出
3 × 3、2 × 2、1 × 1、1 × 1 共 4 个正方形。
现在小明有一块矩形的材料，两边长分别是 2019 和 324。请问小明最终会
切出多少个正方形？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1
2
3
4
5
6
7
8
9
10
11
12
13

2.解题代码

package javac_9_19;

public class Test02 {
	// 答案: 21
	public static void main(String[] args) {
		int x = 2019;
		int y = 324;
//		int x = 5; 
//		int y = 3;
		System.out.println(f(x, y, 0));
		
	}
	public static int f(int x , int y , int count) {
		if(x==0 || y==0){
			return count;
		}
		if(x >= y){
			return f((x-y), y , ++count);
		} else {
			return f(x, (y-x), ++count);
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

三、不同子串

1.题目详情

试题 C: 不同子串
本题总分：10 分
【问题描述】
一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成
的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。
注意在计算时，只算本质不同的串的个数。
请问，字符串0100110001010001 有多少个不同的非空子串？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1
2
3
4
5
6
7
8
9
10

2.解题代码

方法： set集合，不能存在相同元素的特性，可以用这个特性获得不同子串

package javac_9_19;

import java.util.HashSet;
import java.util.Set;

public class Test03 {
	// 答案: 100
	public static void main(String[] args) {
		String str = "0100110001010001";
//		String str = "aaab";
		Set<String> set = new HashSet<String>();
		for (int i = 0; i <= str.length(); i++) {
			for (int j = i+1; j <= str.length(); j++) {
				System.out.println(str.substring(i, j));
				set.add(str.substring(i, j));
			}
		}
		
//		for (String string : set) {
//			System.out.print(string + " ");
//		}
		
		System.out.println(set.size());
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

四、质数

1.题目详情

试题 D: 质数
本题总分：10 分
【问题描述】
我们知道第一个质数是 2、第二个质数是 3、第三个质数是 5……请你计算
第 2019 个质数是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1
2
3
4
5
6
7
8

2.解题代码

方法： 判断一个数是否是质数方法很多，可以自行搜索使用

package javac_9_19;

public class Test04 {
	// 答案： 17569
	public static void main(String[] args) {
		int count = 1;
		for (int i = 1; i <= 2019; i++) {
			for (int j = count+1; ; j++) {
				if (f(j)) {
					count = j;
					break;
				}
			}
		}
		System.out.println(count);
	}
	
	/**
	 * 判断一个数是否是质数
	 * @param x
	 * @return
	 */
	public static boolean f(int x) {
		if (x < 3) {
			return (x > 1);
		}
		for (int i = 2; i <= Math.sqrt(x); i++) {
			if (x % i == 0) {
				return false;
			}
		}
		return true;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

五、最大降雨量

1.题目详情

试题 E: 最大降雨量
本题总分：15 分
【问题描述】
由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。
这个法术需要用到他手中的 49 张法术符，上面分别写着 1 至 49 这 49 个
数字。法术一共持续 7 周，每天小明都要使用一张法术符，法术符不能重复使
用。
每周，小明施展法术产生的能量为这周 7 张法术符上数字的中位数。法术
施展完 7 周后，求雨将获得成功，降雨量为 7 周能量的中位数。
由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
1
2
3
4
5
6
7
8
9
10
11
12
13

2.解题代码

package javac_9_19;

public class Test05 {
	// 答案34
	public static void main(String[] args) {
		System.out.println(49-16+1);
	}
}
   
1
2
3
4
5
6
7
8
9

图片:

---

六、旋转

1.题目详情

试题 F: 旋转
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分
【问题描述】
图片旋转是对图片最简单的处理方式之一，在本题中，你需要对图片顺时
针旋转 90 度。
我们用一个 n × m 的二维数组来表示一个图片，例如下面给出一个 3 × 4 的
图片的例子：
1 3 5 7
9 8 7 6
3 5 9 7
这个图片顺时针旋转 90 度后的图片如下：
3 9 1
5 8 3
9 7 5
7 6 7
给定初始图片，请计算旋转后的图片。
【输入格式】
输入的第一行包含两个整数 n 和 m，分别表示行数和列数。
接下来 n 行，每行 m 个整数，表示给定的图片。图片中的每个元素（像
素）为一个值为 0 至 255 之间的整数（包含 0 和 255）。
【输出格式】
输出 m 行 n 列，表示旋转后的图片。
【样例输入】
3 4
1 3 5 7
9 8 7 6
3 5 9 7
【样例输出】
3 9 1
5 8 3
9 7 5
7 6 7
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ n, m ≤ 10。
对于 60% 的评测用例，1 ≤ n, m ≤ 30。
对于所有评测用例，1 ≤ n, m ≤ 100。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2.解题代码

方法： 找的旋转i和j的关系

package javac_9_19;

import java.util.Scanner;

public class Test06 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int [][] arr = new int[n+1][m+1];
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j < arr[i].length; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		int [][] brr = new int[m+1][n+1];
		// 转换
		for (int i = 1; i < brr.length; i++) {
			for (int j = 1; j < brr[i].length; j++) {
				brr[i][j] = arr[n-j+1][i]; 
			}
		}
		// 打印
		for (int i = 1; i < brr.length; i++) {
			for (int j = 1; j < brr[i].length; j++) {
				System.out.print(brr[i][j]+" ");
			}
			System.out.println();
		}
		sc.close();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

七、外卖店优先级

1.题目详情

试题 G: 外卖店优先级
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有
一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减
到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果
优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优
先缓存中。
【输入格式】
第一行包含 3 个整数 N、M 和 T。
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到
一个订单。
【输出格式】
输出一个整数代表答案。
【样例输入】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
【样例输出】
1
【样例解释】
6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，
加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。
【评测用例规模与约定】
对于 80% 的评测用例，1 ≤ N, M, T ≤ 10000。
对于所有评测用例，1 ≤ N, M, T ≤ 100000，1 ≤ ts ≤ T，1 ≤ id ≤ N
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2.解题代码

package javac_9_19;

import java.util.Scanner;

public class Test07 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int t = sc.nextInt();
		int [][] arr = new int[n+1][t+1];
		for (int i = 0; i < m; i++) {
			int t1 = sc.nextInt(); // 时刻
			int n1 = sc.nextInt(); // 几店
			arr[n1][t1]++; // n店t时刻的订单数
		}
		int count = 0; // 优先缓存个数
		// 对每家店进行计算
		for (int i = 1; i <= n; i++) { 
			int num = 0; // 缓存值
			boolean f = false; // 判断是否是优先缓存
			for (int j = 1; j <= t; j++) {
				if (arr[i][j] == 0) { // 没有订单时
					if (num <= 0) {
						num = 0;
					} else {
						num--;
					}
				} else {
					num += 2 * arr[i][j]; // 有订单时：缓存值是每个订加2
				}
				if (num > 5) {
					f = true;
				}
				if (num <= 3) {
					f = false;
				}
			}
			if (f) {
				count++;
			}
		}
		System.out.println(count);
		sc.close();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

八、人物相关性分析

1.题目详情

试题 H: 人物相关性分析
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】
小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob
有多少次同时出现。
更准确的说，小明定义 Alice 和 Bob“同时出现”的意思是：在小说文本
中 Alice 和 Bob 之间不超过 K 个字符。
例如以下文本：
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是”Alice and Bob”
和”Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。
注意:
1. Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。
2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能
有字母。例如 Bobbi 並不算出现了 Bob。
【输入格式】
第一行包含一个整数 K。
第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超
过 1000000。
【输出格式】
输出一个整数，表示 Alice 和 Bob 同时出现的次数。
【样例输入】
20
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例，1 ≤ K ≤ 1000000。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.解题代码

方法：.substring()：切割字符串

package javac_9_19;

import java.util.Scanner;

public class Test08 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		sc.nextLine();
		String str = sc.nextLine();

		int count = 0;
		for (int i = 0; i < str.length()-8; i++) {
			if (str.charAt(i) == 'A') {
				String alicestr = str.substring(i, i + 5);
				if (alicestr.equals("Alice")) {
					for (int j = 0; j < K - 3; j++) {
						if (str.charAt(i + j) == 'B') {
							String bobstr = str.substring(i + j, i + j + 3);
							if (bobstr.equals("Bob")) {
								count++;
							}
						}
					}
				}
			}
			if (str.charAt(i) == 'B') {
				String bobstr = str.substring(i, i + 3);
				System.out.println(bobstr);
				if (bobstr.equals("Bob")) {
					for (int j = 0; j < K - 5; j++) {
						if (str.charAt(i + j) == 'A') {
							String alicestr = str.substring(i + j, i + j + 5);
							System.out.println(alicestr);
							if (alicestr.equals("Alice")) {
								count++;
							}
						}
					}
				}
			}
		}
		System.out.println(count);
		sc.close();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

九、等差数列

1.题目详情

试题 I: 等差数列
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
【问题描述】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有
几项？
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN。(注意 A1 ∼ AN 并不一定是按等差数
列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、
18、20。
【评测用例规模与约定】
对于所有评测用例，2 ≤ N ≤ 100000，0 ≤ Ai ≤ 109。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.解题代码

方法： Arrays.sort()：排序

package javac_9_19;

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

public class Test09 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int [] arr = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		// 排序
//		for (int i = 0; i < arr.length-1; i++) {
//			for (int j = 0; j < arr.length-1-i; j++) {
//				if (arr[j] >= arr[j+1]) {
//					int temp = arr[j];
//					arr[j] = arr[j+1];
//					arr[j+1] = temp;
//				}
//			}
//		}
		Arrays.sort(arr); 
		
		// 获取最小差值
		int min = arr[arr.length-1];
		for (int i = 1; i < arr.length; i++) {
			if ((arr[i] - arr[0]) < min) {
				min = (arr[i] - arr[0]);
			}
		}
		System.out.println((arr[arr.length-1]-arr[0])/min+1);
		sc.close();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

十、打扫机器人

1.题目详情

试题 J: 扫地机器人
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
【问题描述】
小明公司的办公区有一条长长的走廊，由 N 个方格区域组成，如下图所
示。
1
2
3
4
5

走廊内部署了 K 台扫地机器人，其中第 i 台在第 Ai 个方格区域中。
已知扫地机器人每分钟可以移动到左右相邻的方格中，并将该区域清扫干
净。
请你编写一个程序，计算每台机器人的清扫路线，使得
1. 它们最终都返回出发方格，
2. 每个方格区域都至少被清扫一遍，
3. 从机器人开始行动到最后一台机器人归位花费的时间最少。
注意多台机器人可以同时清扫同一方块区域，它们不会互相影响。
输出最少花费的时间。
在上图所示的例子中，最少花费时间是 6。第一台路线：2-1-2-3-4-3-2，清
扫了 1、2、3、4 号区域。第二台路线 5-6-7-6-5，清扫了 5、6、7。第三台路线
10-9-8-9-10，清扫了 8、9 和 10。
【输入格式】
第一行包含两个整数 N 和 K。
接下来 K 行，每行一个整数 Ai。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.解题代码

这道题暂时不会，可以去搜这道题的解法。

---