蓝桥杯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();}
}