第10届蓝桥杯JavaB组省赛
其他链接
第11届蓝桥杯JavaB组省赛 - Cattle_Horse
第12届蓝桥杯JavaB组省赛 - Cattle_Horse
第13届蓝桥杯javaB组省赛 - Cattle_Horse
前言
用时及分数
未进行用时测试
感受
看清楚题目！！！
如 \(B\) 题要求字符串为非空的连续字串
如 \(D\) 题要求分解的三个数各不相同
收获
复习了 \(BFS\) 的使用及其路径的输出
试题 A 组队
问题描述
作为篮球队教练，你需要从名单中选出 \(1\) 号位至 \(5\) 号位各一名球员，组成球队的首发阵容。
每位球员担任 \(1\) 号位至 \(5\) 号位时的评分表在 team.txt中。请你计算首发阵容 \(1\) 号位至 \(5\) 号位的评分之和最大可能是多少？
答案：\(490\)
Code
\(DFS\) 遍历每个位置由谁担任
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class Main {
static int ans = 0;
static boolean[] book = new boolean[21];
static int[][] a = new int[21][6];
static void dfs(int now, int sum) {
if (now == 5) {
ans = Math.max(ans, sum);
return;
}
for (int i = 1; i <= 20; ++i) {
if (book[i]) continue;
book[i] = true;
dfs(now + 1, sum + a[i][now]);
book[i] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader(".//team.txt"));
for (int i = 1; i <= 20; ++i) {
String[] num = br.readLine().split(" ");
for (int j = 1; j <= 5; ++j) {
a[i][j] = Integer.parseInt(num[j]);
}
}
for (int i = 1; i <= 20; ++i) {
dfs(1, a[i][1]);
}
System.out.println(ans);//490
}
}
试题 B 不同子串
问题描述
一个字符串的非空子串是指字符串中长度至少为 \(1\) 的连续的一段字符组成的串。例如，字符串aaab 有非空子串 a, b, aa, ab, aaa, aab, aaab，一 共 \(7\) 个。
注意在计算时，只算本质不同的串的个数。
请问，字符串 0100110001010001 有多少个不同的非空子串？
答案：\(100\)
Code
双重循环 + 去重
import java.util.HashSet;
public class Main {
static HashSet<String> set = new HashSet<>();
static String s = "0100110001010001";
public static void main(String[] args) {
int len = s.length();
for (int i = 0; i < len; ++i) {
for (int j = i; j < len; ++j) {
// substring是左闭右开区间
set.add(s.substring(i, j + 1));
}
}
System.out.println(set.size());//100
}
}
试题 C 数列求值
问题描述
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求第 20190324 项的最后 4 位数字。
答案：\(4659\)
思路
方法：
- 使用 \(BigInteger\) 模拟
- 最后四位数字相当于对 \(10000\) 取模（可滚动数组优化）
public class Main {
static final int MOD = (int) 1e4;
static final int N = 20190324;
public static void main(String[] args) {
int[] arr = new int[4];
final int n = 4;
arr[1] = arr[2] = arr[3] = 1;
int now = 4;
while (now <= N) {
arr[now % n] = (arr[(now - 1 + n) % n] + arr[(now - 2 + n) % n] + arr[(now - 3 + n) % n]) % MOD;
++now;
}
System.out.println(arr[N % n]);//4659
}
}
试题 D 数的分解
问题描述
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法？
注 意 交 换 3 个 整 数 的 顺 序 被 视 为 同 一 种 方 法， 例 如 1000+1001+18 和 1001+1000+18 被视为同一种。
答案：\(40785\)
思路
是否包含 \(2\) 和 \(4\) 可用数字循环除 \(10\) 模 \(10\) 来判断
交换顺序被视为同一种方法，使三个数递增的遍历就不会出现重复情况
public class Main {
static final int n = 2019;
static boolean check(int x) {
while (x != 0) {
if (x % 10 == 2 || x % 10 == 4) return true;
x /= 10;
}
return false;
}
public static void main(String[] args) {
int ans = 0;
for (int i = 1; i <= n / 3; ++i) {
if (check(i)) continue;
for (int j = i + 1; j <= n; ++j) {
int k = n - i - j;
if (k <= j) break;
if (check(j)) continue;
if (check(k)) continue;
++ans;
}
}
System.out.println(ans);// 40785
}
}
试题 E 迷宫
问题描述
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于更复杂的迷宫（30 行 50 列 见文件maze.txt），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 D<L<R<U。
答案：DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
思路
思路一：\(DFS\) 遍历所有情况，记录所有能到达终点的步骤，最后取步数最少和字典序最少的步骤
思路二：\(BFS\) 求最短路径，对于字典序最小，可以在每次扩展遍历时，优先选择字典序小的步骤（按 \(D<L<R<U\)）
输出路径需要记录当前的节点是通过哪个步骤过来的，最后递归从终点找起点
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
//按照 DLRU 的顺序bfs,先到的就是步数最少且字典序最小的
static final char[] direction = "DLRU".toCharArray();
static final int[] dx = {1, 0, 0, -1}, dy = {0, -1, 1, 0};
static char[][] map;//迷宫
static final int n = 30, m = 50;
static boolean[][] vis = new boolean[n][m];//标记该点是否走过
static char[][] Path = new char[n][m]; //记录该点是通过什么步骤过来的
static StringBuilder ans = new StringBuilder();
// 从终点dfs回头找起点
static void dfsPath(int x, int y) {
if (x == 0 && y == 0) return;
if (Path[x][y] == 'D') dfsPath(x - 1, y);//原来向下走，现在向上走
else if (Path[x][y] == 'L') dfsPath(x, y + 1);
else if (Path[x][y] == 'R') dfsPath(x, y - 1);
else dfsPath(x + 1, y);
ans.append(Path[x][y]);
}
static void bfs() {
Queue<Point> q = new LinkedList<>();
q.add(new Point(0, 0));
vis[0][0] = true;
while (!q.isEmpty()) {
Point p = q.poll();
int x = p.x, y = p.y;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny)) {
vis[nx][ny] = true;
Path[nx][ny] = direction[i];
if (nx == n - 1 && ny == m - 1) return;
q.add(new Point(nx, ny));
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new FileReader(".//maze.txt"));
map = new char[n][];
for (int i = 0; i < n; ++i) map[i] = in.readLine().toCharArray();
bfs();
dfsPath(n - 1, m - 1);
System.out.println(ans);
}
//检查该点是否可以走
static boolean check(int x, int y) {
return x < n && x >= 0 && y < m && y >= 0 && map[x][y] != '1' && !vis[x][y];
}
}
class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
试题 F 特别数的和
问题描述
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
【输入格式】
输入一行包含两个整数 n。
【输出格式】
输出一行，包含一个整数，表示满足条件的数的和。
【样例输入】
40
【样例输出】
574
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n ≤ 10。
对于 50% 的评测用例，1 ≤ n ≤ 100。
对于 80% 的评测用例，1 ≤ n ≤ 1000。
对于所有评测用例，1 ≤ n ≤ 10000。
思路
枚举模拟
枚举 \(1\sim n\) ，对每个数进行判断是否包含 \(2,0,1,9\)，判断方法与 \(D\) 题相同
时间复杂度：\(O(n\times\sum_{i=1}^{n}digit(i)=nlogn)\)
import java.util.Scanner;
public class Main {
static boolean check(int x) {
while (x != 0) {
int t = x % 10;
if (t == 2 || t == 0 || t == 1 || t == 9) return true;
x /= 10;
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
long ans = 0;
for (int i = 1; i <= n; ++i) {
if (check(i)) ans += i;
}
System.out.println(ans);
}
}
数位DP
从高位到低位选择数字，每个数的权重与其所在位置有关
TODO
试题 G 外卖店优先级
问题描述
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。
【输入格式】
第一行包含 3 个整数 N、 M 和 T 。
以下 M 行每行包含两个整数 t s 和 id，表示 t s 时刻编号 id 的外卖店收到一个订单。
【输出格式】
输出一个整数代表答案。
【样例输入】
266
11
52
31
62
21
62
【样例输出】
1
【样例解释】
6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。
【评测用例规模与约定】
对于 80% 的评测用例，1 ≤ N, M, T ≤ 10000。
对于所有评测用例，1 ≤ N, M, T ≤ 100000，1 ≤ t s ≤ T ，1 ≤ id ≤ N。
思路
TODO
标签：10,int,蓝桥,static,import,new,public,组省赛 From： https://www.cnblogs.com/Cattle-Horse/p/17077480.html