2019年蓝桥杯Java-B组省赛题解
可乐塞满冰
帮助1人
一、组队（贪心）
贪心，每个尽量选最大的，1号编号1：97分，2号编号10：99分，3号编号17：99分，4号编号15：97分，5号编号12：98分，总共：490分答案：490
二、不同子串（substring）
一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如，字符串 aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。 注意在计算时，只算本质不同的串的个数。
请问，字符串0100110001010001 有多少个不同的非空子串？
注意，必须是非空子串。
本题，不能用dfs set去重来解，因为它取出来结果不是子串，而是子集，之前的回溯专题一也从来没有把dfs用于解决子串问题，都是解决组合、排列、子集问题，一定不能混用！
import java.util.*;
public class Main {
static String str = "";
static HashSet<LinkedList<Character>> set = new HashSet<>();
static LinkedList<Character> tmp = new LinkedList<>();
public static void main(String[] args) {
str = "abcd";
dfs(0);
System.out.println(set.size());
}
static void dfs(int start) {
if (tmp.size() > 0) {
System.out.println(tmp);
set.add(new LinkedList<>(tmp));
}
if (tmp.size() > str.length()) {
return;
}
for (int i = start; i < str.length(); i ) {
tmp.add(str.charAt(i));
dfs(i 1);
tmp.removeLast();
}
}
}
正解是用substring直接一个个枚举，加set去重。
import java.util.*;
public class Main {
public static void main(String[] args) {
HashSet<String> set = new HashSet<>();
String str = "0100110001010001";
for (int i = 0; i < str.length(); i ) {
for (int j = i 1; j <= str.length(); j ) {
// substring(i,j) => str[i,j)，左闭右开
System.out.println(str.substring(i, j));
set.add(str.substring(i, j));
}
}
System.out.println(set.size());
}
}
答案：100
三、数列求值（模拟）
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个 4 位整数（提示：答案的千位不为 0），在提交答案时只填写这个整数，填写 多余的内容将无法得分。
f(n) = f(n - 1) f(n - 2) f(n - 3)，只要最后4位数，每次对10000取余。
import java.util.*;
public class Main {
public static void main(String[] args) {
int a = 1;
int b = 1;
int c = 1;
int res = 0;
for (int i = 4; i <= 20190324; i ) {
int tmp = (a b c) % 10000;
res = tmp;
c = b;
b = a;
a = tmp;
}
System.out.println(res);
}
}
注意，有些同学不对10000取余，计算出来结果是不对的，因为数字太大已经超出int表示范围，你在控制台看到的数字是错误的。（要么使用BigInteger）
答案：4659
四、数的分解（模拟）
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法？
注意交换 3 个整数的顺序被视为同一种方法，例如 1000 1001 18 和 1001 1000 18 被视为同一种。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
注意交换 3 个整数的顺序被视为同一种方法，那保证三个数字的大小关系即可。
import java.util.*;
public class Main {
public static void main(String[] args) {
int ans = 0;
for (int i = 1; i <= 2019; i ) {
if (!check(i)) {
continue;
}
for (int j = i 1; j <= 2019; j ) {
if (!check(j)) {
continue;
}
for (int k = j 1; k <= 2019; k ) {
if (!check(k)) {
continue;
}
if (i j k == 2019) {
ans ;
System.out.println(i " " j " " k "=" "2019");
}
}
}
}
System.out.println(ans);
}
static boolean check(int n) {
while (n != 0) {
if (n % 10 == 2 || n % 10 == 4) {
return false;
}
n /= 10;
}
return true;
}
}
答案：40785
五、迷宫（BFS）
下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
注意题目中，使用步数最少，那就得用BFS，并且要保证字典序最小，那就是按照给定的字典序来移动，记录下每次移动的方位即可。
BFS特点：不需要回溯，第一个到达的就是步数最少的。
import java.util.*;
// 放入Queue的结点
class node {
int x, y;
// 用String类，而不是List类！
String move;
node () {};
node (int x, int y, String move) {
this.x = x;
this.y = y;
this.move = move;
}
}
public class Main {
static char[][] map = new char[30][50];
static int[][] vis = new int[30][50];
// D L R U
static int[] x = new int[] {1, 0, 0, -1};
static int[] y = new int[] {0, -1, 1, 0};
static char[] dir = new char[] {'D','L','R','U'};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
for (int i = 0; i < 30; i ) {
map[i] = scan.next().toCharArray();
}
// 迷宫的入口为左上角，出口为右下角
node b = new node(0, 0, "");
vis[0][0] = 1;
// 链队
Queue<node> Q = new LinkedList<>();
// 开始结点入队
Q.offer(b);
while (!Q.isEmpty()) {
// 出队
node tmp = Q.poll();
// 到达终点
if (tmp.x == 29 && tmp.y == 49) {
System.out.println(tmp.move);
}
for (int i = 0; i < 4; i ) {
node temp = new node();
temp.x = tmp.x x[i];
temp.y = tmp.y y[i];
if (temp.x < 0 || temp.y < 0 || temp.x >= 30 || temp.y >= 50 || vis[temp.x][temp.y] == 1 || map[temp.x][temp.y] == '1') {
continue;
}
// bfs不需要回溯
vis[temp.x][temp.y] = 1;
String moveTemp = tmp.move dir[i];
temp.move = moveTemp;
// 入队
Q.offer(temp);
}
}
}
}
注意，String类、List类，在赋值时，List move = list，传递的是一个引用，move一旦add后，list中也会被add，所以，一定要注意这种引用类型数据的使用，不要因为这些产生错误，String类进行加减时，是生成新的字符串，而不是覆盖原先字符串。所以上面的代码的node类中才使用String记录答案，之前用的List，导致结果一直不正确，搞半天是引用问题。
答案：
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
六、特别数的和（模拟）
看了下数据范围，直接模拟即可。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int sum = 0;
for (int i = 1; i <= n; i ) {
if (check(i)) {
sum = i;
}
}
System.out.println(sum);
}
static boolean check (int n) {
// 不包括前导0
while (n != 0) {
int rar = n % 10;
if (rar == 2 || rar == 0 || rar == 1 || rar == 9) {
return true;
}
n /= 10;
}
return false;
}
}
七、外卖店优先级（排序、模拟）
这个题跟18年的日志统计很像，但不用滑动窗口，java有map、set，直接模拟就行。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
// n家外卖店
int n = scan.nextInt();
// m条订单信息
int m = scan.nextInt();
// t时刻以内
int t = scan.nextInt();
int[] ids = new int[m 1];
HashMap<Integer, LinkedList<Integer>> map = new HashMap<>();
for (int i = 0; i < m; i ) {
// ts时刻
int ts = scan.nextInt();
// id编号的外卖店收到一个订单
int id = scan.nextInt();
// 记录id
ids[i] = id;
// 记录下时间
if (map.containsKey(id)) {
LinkedList<Integer> tmp = map.get(id);
tmp.add(ts);
map.put(id, tmp);
} else {
LinkedList<Integer> tmp = new LinkedList<>();
tmp.add(ts);
map.put(id, tmp);
}
}
// 排序方便去重
Arrays.sort(ids);
// set记录有多少外卖店id满足
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < m; i ) {
// 之前开的ids数组中有0的位置，要去掉
if (ids[i] == 0) {
continue;
}
// 去重
if (i > 0 && ids[i] == ids[i - 1]) {
continue;
}
LinkedList<Integer> tmp = map.get(ids[i]);
// 记录每个id的时间订单数
int[] times = new int[t 1];
for (int j = 0; j < tmp.size(); j ) {
times[tmp.get(j)] ;
}
// 统计优先级
int cnt = 0;
// 时刻表：从 1 到 t
for (int j = 1; j <= t; j ) {
if (times[j] == 0) {
if (cnt > 0) {
cnt--;
}
} else {
// 每一单优先级 2
cnt = times[j] * 2;
}
if (cnt > 5) {
if (!set.contains(ids[i])) {
set.add(ids[i]);
}
}
if (cnt <= 3) {
if (set.contains(ids[i])) {
set.remove(ids[i]);
}
}
}
}
System.out.println(set.size());
}
}
模拟题，最重要的是仔细，仔细，一定要仔细，因为它的数据量就适合模拟，直接仔细点写出来就行。
八、人物相关性分析（indexOf、模拟）
先记录下Alice、Bob的下标，然后遍历两个下标的位置，统计index的差是否小于等于k。
难点主要在于确定单词下标，和判断当前单词是不是符合Alice和Bob。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
// nextLine是读取带空格字符串，如果用了nextLine，所有的读入最好都用nextLine
String k = scan.nextLine();
int gap = Integer.parseInt(k);
String str = scan.nextLine();
List<Integer> aliceIndex = new ArrayList<>();
List<Integer> bobIndex = new ArrayList<>();
// 统计alice的下标
int index = -1;
while (true) {
// 后面的index 1参数是指从哪个下标开始
// indexOf找不到就返回 - 1
index = str.indexOf("Alice", index 1);
if (index == -1) {
break;
}
// 如果Alice前后不是单词那就可以算是单独的一个单词
// 如果Alice前后是单词，那就不算
if (index != 0 && check(str.charAt(index - 1))) {
continue;
}
if (index != str.length() - 5 && check(str.charAt(index 5))) {
continue;
}
// 记录下alice单词的开始下标
aliceIndex.add(index);
}
index = -1;
while (true) {
// 后面的index 1参数是指从哪个下标开始
// indexOf找不到就返回 - 1
index = str.indexOf("Bob", index 1);
if (index == -1) {
break;
}
if (index != 0 && check(str.charAt(index - 1))) {
continue;
}
if (index != str.length() - 3 && check(str.charAt(index 3))) {
continue;
}
bobIndex.add(index);
}
int ans = 0;
// 注意可以一个Alice对应多个Bob，可以一个Bob对应多个Alice
for (int i = 0; i < aliceIndex.size(); i ) {
for (int j = 0; j < bobIndex.size(); j ) {
if (aliceIndex.get(i) > bobIndex.get(j)) {
int tmp = aliceIndex.get(i) - bobIndex.get(j) - 3;
if (tmp <= gap) {
ans ;
}
} else {
int tmp = bobIndex.get(j) - aliceIndex.get(i) - 5;
if (tmp <= gap) {
ans ;
}
}
}
}
System.out.println(ans);
}
static boolean check(char c) {
if (c >= 'a' && c <= 'z') return true;
if (c >= 'A' && c <= 'Z') return true;
return false;
}
}
蓝桥杯的这道题测试样例有问题，在Acwing上跑的，样例数据达到最大时会超时。
九、后缀表达式（后缀表达式、数学推导）
自己做不来，看了别人的题解，地址：https://www.acwing.com/problem/content/description/1249/
因为是凑成后缀表达式，由于后缀表达式会去除括号，题目只需要满足正负号要求，所以无论有几个负号，都可以转换为只有1个负号的情况（就是通过添加括号实现）。
例如一个负号，=a1 a2 a3 - a4，两个负号，=a1 a2 - (a3 a4)，三个负号，=a1 - (a2 a3 a4)，是不是很神奇，所以我们只用考虑1个负号和0个负号的情况，0个负号好求，直接全部加起来，1个负号呢？
把数组从大到小排序，可以分为三种情况，全正数、全负数、有正有负（如上图），归结出来都可以用一个公式求得：abs(a1-a6) abs(ai)，问题就变得简单了。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
long[] nums = new long[n m 1];
for (int i = 0; i < n m 1; i ) {
nums[i] = scan.nextLong();
}
long sum = 0;
// 只用讨论1个负号、0个负号
if (m == 0) {
for (int i = 0; i < n m 1; i ) {
sum = nums[i];
}
} else {
Arrays.sort(nums);
sum = Math.abs(nums[0] - nums[n m]);
for (int i = 1; i < n m; i ) {
sum = Math.abs(nums[i]);
}
}
System.out.println(sum);
}
}
十、灵能传输
俺不会。
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhgehhhb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01
