转载

蓝桥杯第十届省赛Java-B组

作为篮球队教练，你需要从以下名单中选出1 号位至5 号位各一名球员，

组成球队的首发阵容。

每位球员担任1 号位至5 号位时的评分如下表所示。请你计算首发阵容1

号位至5 号位的评分之和最大可能是多少？

蓝桥杯第十届省赛Java-B组

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解题思路：

该题很简单。仔细找找就出来了。先找出每列最大的两个数，然后综合找出最大的5个。

蓝桥杯第十届省赛Java-B组

答案：

490

2.不同的子串：

一个字符串的非空子串是指字符串中长度至少为1 的连续的一段字符组成

的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共7 个。

注意在计算时，只算本质不同的串的个数。

请问，字符串0100110001010001 有多少个不同的非空子串？

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解题思路：

这是求串的所有子集，并且所有相同的子串算一种。

我解该题的思路是，将所有可能的子串都加入到hashset集合中。最后返回set集合的元素个数。因为hashset会自动排除重复元素。

代码示例：

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

public class 子串的数量 {

	public static void main(String[] args) {
		String s1 = "aaab";
		String s2 = "0100110001010001";
		System.out.println(subSum(s1));
		System.out.println(subSum(s2));

	}
	
	public static int subSum(String s) {
		Set<String> set = new HashSet<String>();
		for(int i = 0; i < s.length(); i++) {
			for(int j = i ; j < s.length(); j++) {
				//将每一个子串都加入到set集合中
				set.add(s.substring(i, j + 1 ));
			}
		}
		return set.size();
	}
}

程序运行结果：

本题答案：

100

3.数列求值：

给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求

第20190324 项的最后4 位数字。

解题思路：

使用迭代法，因为数字太大，每次对10000取余。

代码示例：

public class 数列求值 {

	public static void main(String[] args) {
		int n = 20190324;
		int a = 1;
		int b = 1;
		int c = 1;
		for(int i = 4; i <= n; i++) {
			if(i % 3 == 1) {
				a = (a + b + c) % 10000;
			}else if(i % 3 == 2) {
				b = (a + b + c) % 10000;
			}else {
				c = (a + b + c) % 10000;
			}
		}
		if(n % 3 == 1) {
			System.out.println(a);
		}else if( n % 3 == 2) {
			System.out.println(b);
		}else {
			System.out.println(c);
		}
	}
}

答案：

4659

4.数的分解：

把2019 分解成3 个各不相同的正整数之和，并且要求每个正整数都不包

含数字2 和4，一共有多少种不同的分解方法？

注意交换3 个整数的顺序被视为同一种方法，例如1000+1001+18 和

1001+1000+18 被视为同一种。

解题思路：

首先开辟一个2020的数组，用来标记每个数中是否包含2和4。通过这样的标记，可以在判断是可以直接返回，大大加快程序执行速度。

代码示例：

public class 数的分解 {

	static int[] a = new int[2019 + 1];
	public static void main(String[] args) {
		int n = 2019;
		//初始化处理1-2019的数字，如果数字标记为1，则有
		for(int i = 1; i < a.length; i++) {
			a[i] = 1;
			char[] s = String.valueOf(i).toCharArray();
			for(int b = 0; b < s.length; b++) {
				if(s[b] == '2' || s[b] == '4') {
					a[i] = 0;
					break;
				}
			}
		}
		int cnt = 0;
		for(int a = 1; a < n / 3 + 1; a++) {
			if(check(a)) {
				for(int b = a + 1; b < n; b++) {
					if(check(b)) {
						for(int c = b + 1; c < n; c++) {
							if(a + b + c > n) {
								break;
							}
							if(check(c)) {
								if(a + b + c == n) {
									cnt++;
								}
							}
						}
					}
				}
			}
		}
		System.out.println(cnt);
	}
	
	//判断i中的数字是否有2 或者4
	private static boolean check(int i) {
		if(a[i] == 1) {
			return true;
		}else {
			return false;
		}
	}
}

答案：

40785

5.迷宫：

下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可

以通行的地方。

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这

个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，

一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，

其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。

请注意在字典序中D<L<R<U。

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个字符串，包含四种字母D、U、L、R，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

6.特别数的和：

小明对数位中含有2、0、1、9 的数字很感兴趣（不包括前导0），在1 到

40 中这样的数包括1、2、9、10 至32、39 和40，共28 个，他们的和是574。

请问，在1 到n 中，所有这样的数的和是多少？

输入：

输入一行包含一个整数n。

输出：

输出一行，包含一个整数，表示满足条件的数的和。

【样例输入】

【样例输出】

574

解题思路：

这道题比较简单，直接判断1-n中的每位数字是否包含2/0/1/9数字，如果包含累加即可。

代码示例：

import java.util.Scanner;

public class 特别数的和 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int sum = 0;
		for(int i = 1; i <= n; i++) {
			if(check(i)) {
				sum += i;
			}
		}
		System.out.println(sum);
	}

	private static boolean check(int i) {
		char[] s = String.valueOf(i).toCharArray();
		for(int b = 0; b < s.length; b++) {
			if(s[b] == '2' || s[b] == '0' || s[b] == '1' || s[b] == '9') {
				return true;
			}
		}
		return false;
	}

}

7.外卖店优先级：

“饱了么”外卖系统中维护着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 号) 在优先缓存中。

代码示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class 外卖店优先级 {

	static int N;
	static int M;
	static int T;
	static int[][] table;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		T = sc.nextInt();
		table = new int[M][2];
		//id集合，用来存放商家的id号
		Set<Integer> idset = new HashSet<Integer>();
		for(int i = 0; i < M; i++) {
			table[i][0] = sc.nextInt();
			table[i][1] = sc.nextInt();
			idset.add(table[i][1]);
		}
		//缓存列表
		Set<Integer> cache = new HashSet<Integer>();
		for(Integer id : idset) {
			//用来存放每个商家的订单
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			for(int i = 0; i < M; i++) {
				if(table[i][1] == id) {
					tmp.add(table[i][0]);
				}
			}
			int pre = 0;//外卖店的优先级
			Collections.sort(tmp);
			for(int ts = 1; ts <= T; ts++) {
				//判断外卖店中ts时刻是否有订单
				if(tmp.contains(ts)) {//有订单
					for(int t = 0; t < tmp.size(); t++) {
						if(tmp.get(t) == ts) {
							pre += 2;
						}else if(tmp.get(t) > ts){
							break;
						}else {
							continue;
						}
					}
					if(pre > 5) {
						cache.add(id);
					}
				}else {//无订单
					if(pre >= 1) {
						pre -= 1;
					}else {
						pre = 0;
					}
					if(pre <= 3) {
						cache.remove(id);
					}
				}
			}
		}	
		System.out.println(cache.size());
	}

}

8.人物相关性分析：

【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中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 个字符。 注意:
Alice 和Bob 是大小写敏感的，alice 或bob 等并不计算在内。
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

9.后缀表达式：

【问题描述】

给定N 个加号、M 个减号以及N + M + 1 个整数A1; A2; ; AN+M+1，小

明想知道在所有由这N 个加号、M 个减号以及N + M +1 个整数凑出的合法的

后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用1 2 3 + -，则“2 3 + 1 -” 这个后缀表达式结果是4，是最大的。

【输入格式】

第一行包含两个整数N 和M。

第二行包含N + M + 1 个整数A1; A2; ; AN+M+1。

【输出格式】

输出一个整数，代表答案。

【样例输入】

1 1

1 2 3

【样例输出】

代码示例：

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

public class 后缀表达式 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[n +m + 1];
		for(int i = 0; i < n + m + 1; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		int sum = 0;
		for(int i = n + m; i >= 0; i--) {
			if(i >= n) {
				sum += a[i];
			}else {
				sum -= a[i];
			}
		}
		System.out.println(sum);
	}
}