蓝桥杯31天真题冲刺|题解报告|第二十九天

大家好，我是snippet，今天是我们刷题的第二十九天，今天主打打比赛，牛客+AcWing+力扣，今天的牛客是真的有趣，下面是我今天AcWing周赛的题解

目录

一、热身计算

题目链接：4944. 热身计算 - AcWing题库

题目内容：

解题思路：

代码：

二、比大小

题目链接：4945. 比大小 - AcWing题库

题目内容：

解题思路：

代码：

三、叶子节点

题目链接：4946. 叶子节点 - AcWing题库

题目内容：

解题思路：

代码：

---

一、热身计算

题目链接：4944. 热身计算 - AcWing题库

题目内容：

给定两个正整数 a,b，请你分别计算 min(a,b) 以及 ⌊|a−b|/2⌋ 的值。

⌊|a−b|/2⌋ 表示不大于 |a−b|/2 的最大整数。

输入格式

共一行，包含两个正整数 a,b。

输出格式

共一行，输出两个整数，分别表示 min(a,b) 以及 ⌊|a−b|/2⌋。

数据范围

所有测试点满足 1≤a,b≤100。

输入样例1：

3 1

输出样例1：

1 1

输入样例2：

2 3

输出样例2：

2 0

输入样例3：

7 3

输出样例3：

3 2

解题思路：

直接暴力数学计算

代码：

package 蓝桥杯31天真题冲刺.Day29.AcWing第97场周赛;import java.io.*;/*** @author snippet* @data 2023-04-01* AcWing第97场周赛-热身计算*/
public class T1_热身计算 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int a,b;public static void main(String[] args) throws IOException {String[] s = br.readLine().split(" ");a = Integer.parseInt(s[0]);b = Integer.parseInt(s[1]);pw.print(Math.min(a,b) + " " + (Math.abs(a-b))/2);pw.flush();br.close();}
}

二、比大小

题目链接：4945. 比大小 - AcWing题库

题目内容：

给定一个 n 位 bx 进制数 X 和一个 m 位 by 进制数 Y。

X 和 Y 都为正整数，且都不含前导 00。

请你比较它们的大小。

输入格式

第一行包含两个整数 n,bx。

第二行包含 n 个整数 x1,x2,…,xn，表示 X 的各位数字，它们按照从最高有效位到最低有效位的顺序给出。

第三行包含两个整数 m,by。

第四行包含 m 个整数 y1,y2,…,ym，表示 Y 的各位数字，它们按照从最高有效位到最低有效位的顺序给出。

X 和 Y 的各位数字在输入中均按十进制表示给出。

输出格式

共一行：

如果 X<Y，则输出 <。

如果 X>Y，则输出 >。

如果 X=Y，则输出 =。

数据范围

前 66 个测试点满足 2≤bx,by≤16。
所有测试点满足 1≤n,m≤10，2≤bx,by≤40，bx≠by，0≤xi<bx，0≤yi<by。

输入样例1：

6 2
1 0 1 1 1 1
2 10
4 7

输出样例1：

=

输入样例2：

3 3
1 0 2
2 5
2 4

输出样例2：

<

输入样例3：

7 16
15 15 4 0 0 7 10
7 9
4 8 0 3 1 5 0

输出样例3：

>

解题思路：

根据进制转换的规律，把这些数转为10进制数再进行比较就可以了

代码：

package 蓝桥杯31天真题冲刺.Day29.AcWing第97场周赛;import java.io.*;/*** @author snippet* @data 2023-04-01* AcWing第97场周赛-比大小*/
public class T2_比大小 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int n,m,bx,by;static int[] x = new int[11];static int[] y = new int[11];public static void main(String[] args) throws IOException {String[] s = br.readLine().split(" ");n = Integer.parseInt(s[0]);bx = Integer.parseInt(s[1]);s = br.readLine().split(" ");long ans1 = 0;for (int i = 1; i <= n; i++) {x[i] = Integer.parseInt(s[i-1]);ans1 += x[i] * Math.pow(bx,(n-i));}s = br.readLine().split(" ");m = Integer.parseInt(s[0]);by = Integer.parseInt(s[1]);s = br.readLine().split(" ");long ans2 = 0;for (int i = 1; i <= m; i++) {y[i] = Integer.parseInt(s[i-1]);ans2 += y[i] * Math.pow(by,(m-i));}if (ans1 == ans2) pw.println("=");else if (ans1 > ans2) pw.println(">");else pw.println("<");pw.flush();br.close();}
}

三、叶子节点

题目链接：4946. 叶子节点 - AcWing题库

题目内容：

给定一棵 n个节点的树，节点编号 1∼n。

11 号节点为树的根节点。

每个节点要么是黑色的，要么是白色的。

对于一个叶子节点，如果从该节点到根节点的路径（包括两端节点）中有超过 m 个黑色节点连续的排列在一起，则称该节点为无效叶子节点。

有效叶子节点数量 = 总叶子节点数量 - 无效叶子节点数量

请你统计，给定树中有效叶子节点的数量。

输入格式

第一行包含两个整数 n,m。

第二行包含 n 个整数 a1,a2,…,an，其中 ai 表示第 i 个节点的颜色，1 表示黑色，0 表示白色。

接下来 n−1 行，每行包含两个整数 x,y，表示节点 x 和节点 y 之间存在一条无向边。

保证输入给定的是一棵树。

输出格式

一个整数，表示给定树中有效叶子节点的数量。

数据范围

前 66 个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤10^5，1≤m≤n，0≤ai≤1，1≤x,y≤n，x≠y。

输入样例1：

4 1
1 1 0 0
1 2
1 3
1 4

输出样例1：

2

输入样例2：

7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

输出样例2：

2

解题思路：

建图存储数据，再对图进行搜索，（这个题在比赛的时候想到了思路 没写出来 后面看了题解之后才AC的）

代码：

package 蓝桥杯31天真题冲刺.Day29.AcWing第97场周赛;import java.io.*;
import java.util.ArrayList;
import java.util.List;/*** @author snippet* @data 2023-04-01* AcWing第97场周赛-叶子节点*/
public class T3_叶子节点 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int n,m,ans;static int N = (int) (1e5+10);static int[] color = new int[N];// 每个位置的颜色 0为白色 1为黑色// 用图来存数据static List<List<Integer>> graph = new ArrayList<>();static void dfs(int node, int parent, int cnt, boolean flag) {int child_black = 0;for (int child : graph.get(node)) {if (child != parent) {child_black++;// 如果这个点为白色 则重新计数if (color[node] == 0) cnt = 0;// 如果黑色的连续数超过规定数m时 直接returnif (cnt + color[node] > m) return;dfs(child, node, cnt+color[node], flag);}}if (child_black == 0 && cnt + color[node] <= m && flag) ans++;}public static void main(String[] args) throws IOException {String[] s = br.readLine().split(" ");n = Integer.parseInt(s[0]);m = Integer.parseInt(s[1]);s = br.readLine().split(" ");for (int i = 1; i <= n; i++) {// 1是黑色 0是白色color[i] = Integer.parseInt(s[i-1]);}for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int i = 1; i < n; i++) {s = br.readLine().split(" ");int a = Integer.parseInt(s[0]);int b = Integer.parseInt(s[1]);graph.get(a).add(b);graph.get(b).add(a);}dfs(1, -1, 0, true);pw.println(ans);pw.flush();br.close();}
}