2019 第十届蓝桥杯大赛软件类省赛 Java A组
试题A
题解
题目最后一句贴心的提示选手应该使用 long (C/C++ 应该使用 long long)。
本题思路很直白，两重循环。外层循环 1 到 2019，内层循环检验是否含有 2、0、1、9 这四个数字。
赛场上还可以将数字转换为字符串，利用 String.contains() 快速写出代码，虽然时间复杂没有改变，但应付填空题足矣。
代码
public static void questionA() {
long sum = 0;
for (int i = 1; i <= 2019; i++) {
String int2str = String.valueOf(i);
if (int2str.contains("2") || int2str.contains("0") || int2str.contains("1") || int2str.contains("9"))
sum += i * i;
}
System.out.println(sum);
}
答案
2658417853
试题B
题解
递推数列，从第四项开始，每项都是前三项的和。
易得到递推式 \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\)
代码
public static void questionB() {
int a, b, c, d;
a = b = c = d = 1;
for (int i = 4; i <= 20190324; i++) {
d = (a + b + c) % 10000;
a = b;
b = c;
c = d;
}
System.out.println(d);
}
答案
4659
试题C
题解
本题使用广度优先搜索即可。
代码
private static void questionC() throws IOException {
int n = 30;
int m = 50;
FileReader fr = new FileReader(new File("maze.txt"));
char[][] board = new char[n][m];
for (int i = 0; i < board.length; i++) {
fr.read(board[i]);
// 读取换行符和回车，避免读入到 board 中
fr.read(); fr.read();
}
Queue<Node> queue = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
queue.add(new Node(0, 0));
visited[0][0] = true;
int[][] way = new int[n][m]; // 记录到达 (i, j) 的方式
int[][] delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char[] cc = {'D', 'U', 'R', 'L'};
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (int i = 0; i < 4; i++) {
int x = cur.x + delta[i][0];
int y = cur.y + delta[i][1];
if (x >= 0 && x < n && y >= 0 && y < m && board[x][y] != '1' && !visited[x][y]) {
queue.add(new Node(x, y));
way[x][y] = i;
visited[x][y] = true;
}
}
}
int x = n - 1;
int y = m - 1;
StringBuilder sb = new StringBuilder();
while (x != 0 || y != 0) {
int i = way[x][y];
sb.append(cc[i]);
x -= delta[i][0];
y -= delta[i][1];
}
System.out.println(sb.reverse());
}
static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
答案
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRUUURRRRDDDDRDRRRRRURRRDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
试题D
题解
假设每周的数字从周一到周日递增，每周周四的数字从第一周到第七周递增。
则第四周周四的数字即为降雨量。
又知下面表格中 15 个 \(\$\) 上的数字必大于 \(x\) 。
故 \(x \leq 49 - 15 = 34\)
| 周一 | 周二 | 周三 | 周四 | 周五 | 周六 | 周日 | |
|---|---|---|---|---|---|---|---|
| 第一周 | |||||||
| 第二周 | |||||||
| 第三周 | |||||||
| 第四周 | \(x\) | $ | $ | $ | |||
| 第五周 | $ | $ | $ | $ | |||
| 第六周 | $ | $ | $ | $ | |||
| 第七周 | $ | $ | $ | $ |
答案
34
试题F
题解
完全二叉树除最后一层外，第 n 层的节点数为 \(2^n\)。
我们完全可以利用这个特性，在输入数据时按层统计。
代码
public static void questionF() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int n = 1;
int ans = 0;
int depth = 1;
long maxSum = Long.MIN_VALUE;
while (N > 0) {
long sum = 0;
for (int i = 0; i < n && N > 0; i++) {
sum += sc.nextInt();
N--;
}
if (sum > maxSum) {
maxSum = sum;
ans = depth;
}
n <<= 1;
depth++;
}
System.out.println(ans);
}
试题G
题解
每一个店铺相互独立，可以存储每个店铺的订单时间，判断店铺是否在优先缓存中。
需要注意 T 时刻的优先级判断。
若 T 时刻，优先级 priority > 5，显然位于优先缓存中。
若 T 时刻，优先级 priority == 5，且 T 时刻有一订单，则 T - 1时刻，优先级 priority 为 3，不在优先缓存中。
若 T 时刻，优先级 priority == 4，且 T - 1、T - 2 时刻无订单，则在优先缓存中。
代码
public static void questionG() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int T = sc.nextInt();
ArrayList<Integer>[] store = new ArrayList[N + 1];
while(M-- > 0) {
int ts = sc.nextInt();
int id = sc.nextInt();
if (store[id] == null)
store[id] = new ArrayList<Integer>();
store[id].add(ts);
}
int ans = 0;
for (int id = 1; id <= N; id++) {
if (store[id] == null) continue;
Collections.sort(store[id]);
int lastTime = 0;
int priority = 0;
for (int order = 0; order < store[id].size(); order++) {
int ts = store[id].get(order);
if (ts - lastTime >= 1)
priority -= ts - lastTime - 1;
priority = Math.max(priority, 0);
priority += 2;
lastTime = ts;
}
priority -= T - lastTime;
if (priority > 5
|| (priority == 5 && lastTime != T)
|| (priority == 4 && lastTime < T - 1)
) ans++;
}
System.out.println(ans);
}
试题H
题解
本题可以使用使用并查集可以快速的得到需要修改的数值。
首先对并查集初始化，然后依次读入数字 a。
利用 visited 数组判断该数字 a 是否使用过：若使用过，则利用并查集寻找数字 a 的最大祖先，最大祖先加一即为需要修改的值。若未使用过，则不需要改动。
由此可知，我们的并查集需要单向从小到大。要注意路径压缩。
代码
private static int[] parent = new int[100005];
private static boolean[] visited = new boolean[100005];
public static int find(int x) {
if (x != parent[x])
parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
public static void questionH() {
// 并查集初始化
for (int i = 1; i < parent.length; i++)
parent[i] = i;
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
while (N-- > 0) {
int a = sc.nextInt();
a = visited[a] ? find(a) + 1 : a;
visited[a] = true;
if (a != 1 && visited[a - 1])
parent[a - 1] = a;
if (visited[a + 1])
parent[a] = a + 1;
System.out.print(a + " ");
}
}
试题I
题解
本题为状态压缩动态规划。
因为数据量小，可以使用二进制中的一位表示某袋是否含有糖果。如某一袋糖果为[2 , 3, 5] 可用二进制表示为 0010 0110 （低位在右，高位在左）。
首先定义 dp 数组的含义为 dp[j] 为状态 j 的糖果组合所需要的最小袋数。
base case 为 dp[0] = 0
状态转移方程为 dp[j | candies[i]] = Math.min(dp[j | candies[i]], dp[j] + 1)。
代码
public static void questionI() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[] candies = new int[N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
int candy = sc.nextInt();
candies[i] |= 1 << candy - 1;
}
}
int MAXN = 105;
int[] dp = new int[1 << M];
Arrays.fill(dp, MAXN);
dp[0] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 1 << M; j++) {
if (dp[j] > MAXN)
continue;
dp[j | candies[i]] = Math.min(dp[j | candies[i]], dp[j] + 1);
}
}
if (dp[(1 << M) - 1] < MAXN)
System.out.println(dp[(1 << M) - 1]);
else
System.out.println(-1);
}