PAT (Advanced Level) Practice 1004 Counting Leaves
1004 Counting Leaves
- 题目翻译
- 代码
分数 30
作者 CHEN, Yue
单位 浙江大学
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.
The input ends with N being 0. That case must NOT be processed.
Output Specification:
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.
Sample Input:
2 1
01 1 02
Sample Output:
0 1
题目翻译
背景:
族谱通常由系谱树来表示。你的工作是统计那些没有孩子的家庭成员总数。
输入格式:
每个输入文件包含一个测试用例。每一种情况都以包含以下内容:第一行有一个正整数N(0<N<100),它代表节点的总数,还有一个正整数M,代表不是叶节点的节点总数;然后接着有M行,每一行的格式都是 ID k ID[1] ID[2]…ID[K],其中第一个ID是一个两位数,代表一个给定的非叶节点,K是它的子节点的数量,后面是它的全部子节点的两位数ID序列。为了简单起见,规定根节点的ID为01。
输出格式:
对于每个测试用例,你应该从根节点开始,计算每一层(同辈)的没有孩子的家庭成员总数。结果必须在一行中输出,用空格隔开,并且在每行的末尾不能有额外的空格。示例示例表示一棵只有2个节点的树,其中01是根节点,02是唯一的子节点。因此在根01层上,有0个叶节点;下一层,有1个叶节点。所以应该在一行中输出0 1。
代码
#include <iostream>
#include <string>
#include <stdlib.h>
#include <vector>using namespace std;int maxLevel=0,level[100]={0};
vector<int> tree[100];void dfs(int ID,int curLevel){if(maxLevel<curLevel)maxLevel=curLevel;if(tree[ID].size()>0){for(auto it:tree[ID]){dfs(it,curLevel+1);}}else level[curLevel]++;
}int main(){int n,m;cin>>n>>m;while(m--){int ID,k;cin>>ID>>k;for (int i = 0; i < k; i++) {int temp;cin >> temp;tree[ID].emplace_back(temp);}}dfs(1,1);for (int i = 1; i <= maxLevel; i++) {if (i!=1) cout<<" ";cout << level[i];}}相关文章:
PAT (Advanced Level) Practice 1004 Counting Leaves
1004 Counting Leaves题目翻译代码分数 30 作者 CHEN, Yue 单位 浙江大学 A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child. Input Specification: Each input file contains one test case. Eac…...
基于Redis实现的分布式锁
基于Redis实现的分布式锁什么是分布式锁分布式锁主流的实现方案Redis分布式锁Redis分布式锁的Java代码体现优化一:使用UUID防止误删除优化二:LUA保证删除原子性什么是分布式锁 单体单机部署中可以为一个操作加上锁,这样其他操作就会等待锁释…...
2023年,还找算法岗工作吗?
点击下方卡片,关注“CVer”公众号AI/CV重磅干货,第一时间送达2023年春招(补招)已经大规模启动了!距离2023年暑期实习不到2个月!距离2024届校招提前批不到4个月!距离2024届秋招正式批不到6个月&a…...
正点原子ARM裸机开发篇
裸机就是手动的操作硬件来实现驱动设备,后面会有驱动框架不需要这么麻烦 第八章 汇编 LED 灯实验 核心过程 通过汇编语言来控制硬件(驱动程序) 代码流程 1、使能 GPIO1 时钟 GPIO1 的时钟由 CCM_CCGR1 的 bit27 和 bit26 这两个位控制&…...
20222023华为OD机试 - 压缩报文还原(JS)
压缩报文还原 题目 为了提升数据传输的效率,会对传输的报文进行压缩处理。 输入一个压缩后的报文,请返回它解压后的原始报文。 压缩规则:n[str],表示方括号内部的 str 正好重复 n 次。 注意 n 为正整数(0 < n <= 100),str只包含小写英文字母,不考虑异常情况。 …...
SheetJS的部分操作
成文时间:2023年2月18日 使用版本:"xlsx": "^0.18.5" 碎碎念: 有错请指正。 这个库自说自话升级到0.19。旧版的文档我记得当时是直接写在github的README上。 我不太会使用github,现在我不知道去哪里可以找到…...
pytest总结
这里写目录标题一、pytest的命名规则二、界面化配置符合命名规则的方法前面会有运行标记三、pytest的用例结构三部分组成四、pytest的用例断言断言写法:五、pytest测试框架结构六、pytest参数化用例1、pytest参数化实现方式2、单参数:每一条测试数据都会…...
CNI 网络分析(九)Calico IPIP
文章目录环境流量分析Pod 间Node 到 PodPod 到 serviceNode 到 serviceNetworkPolicy理清和观测网络流量环境 可以看到,在宿主机上有到每个 pod IP 的路由指向 veth 设备 到对端节点网段的路由 指向 tunl0 下一跳 ens10 的 ip 有到本节点网段 第一个 ip 即 tunl0 的…...
分布式任务调度(XXL-JOB)
什么是分布式任务调度? 任务调度顾名思义,就是对任务的调度,它是指系统为了完成特定业务,基于给定时间点,给定时间间隔或者给定执行次数自动执行任务。通常任务调度的程序是集成在应用中的,比如:…...
Django框架之模型视图--Session
Session 1 启用Session Django项目默认启用Session。 可以在settings.py文件中查看,如图所示 如需禁用session,将上图中的session中间件注释掉即可。 2 存储方式 在settings.py文件中,可以设置session数据的存储方式,可以保存…...
二极管的“几种”应用
不知大家平时有没有留意,二极管的应用范围是非常广的,下面我们来看看我想到几种应用,也可以加深对电路设计的认识: A,特性应用: 由于二极管的种类非常之多,这里这个大类简单罗列下:…...
github上传本地文件详细过程
repository 也就是俗称的仓库 声明:后续操作基于win10系统 前提:有一个github账号、电脑安装了git(官方安装地址) 目的: 把图中pdf文件上传到github上的个人仓库中 效果: 温馨提示: git中复制: ctrl insert…...
常用聚类算法分析
1. 什么是聚类 1.1. 聚类的定义 聚类(Clustering)是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起…...
OSG三维渲染引擎编程学习之五十八:“第五章:OSG场景渲染” 之 “5.16 简单光源”
目录 第五章 OSG场景渲染 5.16 简单光源 5.16.1 场景中使用光源 5.16.2 简单光源示例 第五章 OSG场景渲染 OSG存在场景树和渲染树,“场景数”的构建在第三章“OSG场景组...
80211无线网络架构
无线网络架构物理组件BSS(Basic Service Set)基本服务集BSSID(BSS Identification)ssid(Service Set Identification)ESS(Extended Service Set)扩展服务集物理组件 无线网络包含四…...
基于springboot+vue的便利店库存管理系统
基于springbootvue的便利店库存管理系统 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目背景…...
3|物联网控制|计算机控制-刘川来胡乃平版|第1章:绪论|青岛科技大学课堂笔记|U1 ppt
目录绪论(2学时)常用仪表设备(3学时)计算机总线技术(4学时)过程通道与人机接口(6学时)数据处理与控制策略(6学时)网络与通讯技术(3学时࿰…...
js打印本地pdf(使用HttpPrinter打印插件)
js打印本地pdf(使用HttpPrinter打印插件)第一步:启动HttpPrinter打印插件第二步:用浏览器打开示例文件\调用示例\websocket协议示例\html\打印pdf.html输入pdf地址 点击 “下载并打印pdf文件”按钮,就可以静默打印了。…...
华为OD机试 - 双十一(Python) | 机试题算法思路 【2023】
最近更新的博客 【新解法】华为OD机试 - 关联子串 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试 - 停车场最大距离 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试 - 任务调度 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试…...
2020年UML 秋季期末测试题
1.UML的全称是(B )。A.Unified Making LanguageB.Unified Modeling LanguageC.Unified Meodem languageD.Unify Modeling Language2.UML主要应用于( C)。A.基于螺旋模型的结构化开发方法B.基于数据的数据流开发方法C.基于对象的面…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
