小美的树上染色
美团2024届秋招笔试第一场编程真题
先提一个小知识:题目中凡是提到树结构都要使用图的存储方式,只有二叉树例外。
分析:在树结构中,孩子和父节点是相邻节点,而父节点可能有多个孩子节点。在染色的过程中,本质是父子节点满足条件就染成红色。具体染色策略以下图为例
图中节点权值均为1,也就是任意相邻节点都可以满足染色条件,显然我们不能先将a和b染色,那样就只有2个点能被染色,而是应该先染色<f,b>或 <e,b>,然后再<a,c> 或<a,d>,这样可以染4个点。下图又该先考虑染色那些节点呢?
这样总结出贪心策略:先处理叶子结点的染色,然后处理内部节点。比如上图,先处理<g,f>。如果能染色,哪么将g,f标记红色,同时<f,b>就不可能染色了如果不能染色,未来还可以继续试探<f,b>。
实现方法:先处理最外层节点(叶子),外层处理完了,这些叶子就可以不要了,往内层推进。
使用拓扑排序的思想。当然不是入度0节点入队,这可不是有向图。而是度为1(叶子)节点入队,从树叶向树根进行拓扑处理。
图问题的复杂度正常都是遍历所有的结点,也就是访问所有的点和边,此图n-1条边,复杂度为O(n)。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,a[100005],d[100005],red[100005],v[100005],ans=0;
vector <int> e[100005];
bool isP(ll x)/**< 平方数判定 */
{ll y=(int)sqrt(x);return y*y==x;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,x,y;cin>>n;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<n;i++){cin>>x>>y;e[x].push_back(y),e[y].push_back(x);d[x]++,d[y]++;/**< d数组统计度 */}queue<int>q;for(i=1;i<=n;i++)if(d[i]==1)/**< 度为1的入队*/q.push(i);while(q.size())/**< 模拟拓扑排序处理方法 */{x=q.front();v[x]=1;/**< 标记这个节点,避免重新被入队处理 */q.pop();for(i=0;i<e[x].size();i++)/**< 找到x所有邻接点 */{y=e[x][i];if(v[y]) /**< y已经访问过,其实y一定是x的子节点 */continue;if(red[x]==0&&red[y]==0&&isP(a[x]*a[y]))/**< x和它父节点y满足条件 */red[x]=red[y]=1,ans+=2;/**< 标记颜色,计数器+2 */d[y]--;if(d[y]==1)/**< 度为1说明y子节点都处理完了,此时可以入队 */q.push(y);}}cout<<ans;return 0;
}
相关文章:
小美的树上染色
美团2024届秋招笔试第一场编程真题 先提一个小知识:题目中凡是提到树结构都要使用图的存储方式,只有二叉树例外。 分析:在树结构中,孩子和父节点是相邻节点,而父节点可能有多个孩子节点。在染色的过程中,…...
1.rk3588的yolov5运行:pt_onnx_rknn转换及rknn在rk3588系统python运行
自己有点笨,查资料查了一周才完美的实现了yolov5在rk3588环境下的运行,在这里写具体步骤希望大家少走弯路。具体步骤如下: 一、yolov5的原代码下载及pt文件转换为onnx文件 1.yolov5的原代码下载及环境搭建 在这里一定要下载正确版本的源代码…...
适用于全部安卓手机的 5 大免费 Android 数据恢复
您是否面临这样一种情况,即在Android设备上丢失了一些重要文件,但不知道应该选择哪种Android数据恢复来取回它们? 如果您以前从未备份过Android数据,则很难解决问题。 本文将介绍排名前5位的免费Android数据恢复软件。 您可以获…...
【案例分享】BenchmarkSQL 5.0 压测 openGauss 5.0.0
一、前言 本次BenchmarkSQL 压测openGauss仅作为学习使用压测工具测试tpcc为目的,并不代表数据库性能如本次压测所得数据。实际生产性能压测,还需结合服务器软硬件配置、数据库性能参数调优、BenchmarkSQL 配置文件参数相结合,是一个复杂的过…...
Linux之 4 种休眠模式
目录 1. Linux之 4 种休眠模式 1. Linux之 4 种休眠模式 # echo standby >/sys/power/state //CPU和RAM在运行 # echo mem > /sys/power/state //挂起到内存(待机),关闭硬 盘、外设等设备 # echo disk > /sys/power/state //挂起到硬盘(休眠),关闭硬盘、外设等设备&…...
homeassiant主题
下载主题 https://github.com/maartenpaauw/home-assistant-community-themes.git 使用file editor到homeassiant路径下,新建文件夹themes文件夹,用terminal新建也可以。 使用file editor上传文件 使用Terminal解压 mkdir themes unzip home-assistan…...
《2020年最新面经》—字节跳动Java社招面试题
文章目录 前言:一面:01、Java基础知识答疑,简单概述一下?02、倒排索引了解吗?使用Java语言怎么实现倒排?03、详细讲解一下redis里面的哈希表,常用的Redis哈希表命名有哪些,举例说明其…...
2.3IP详解及配置
2.3IP详解及配置 一、ip地址组成 IP地址由4部分数字组成,每部分数字对应于8位二进制数字,各部分之间用小数点分开 这是点分 2进制 如果换算为10进制我们称为点分10进制. 每个ip地址由两部分组成网络地址(NetID)和主z机地址(HostID).网络地址表示其属于…...
Python程序打包指南:手把手教你一步步完成
最近感兴趣想将开发的项目转成Package,研究了一下相关文章,并且自己跑通了,走了一下弯路,这里记录一下如何打包一个简单的Python项目,展示如何添加必要的文件和结构来创建包,如何构建包,以及如何…...
Linux yum 使用时提示 获取 GPG 密钥失败Couldn‘t open file RPM-GPG-KEY-EPEL-7
资料 错误提示: no crontab for root - using an empty one 888 原因剖析: 第一次使用crontab -e 命令时会让我们选择编辑器,很多人会不小心选择默认的nano(不好用),或则提示no crontab for root - usin…...
OpenGL_Learn13(材质)
1. 材质 cube.vs #version 330 core layout (location 0) in vec3 aPos; layout (location 0 ) in vec3 aNormal;out vec3 FragPos; out vec3 Normal;uniform mat4 model; uniform mat4 view; uniform mat4 projection;void main() {FragPosvec3(model*vec4(aPos,1.0));Norma…...
buildadmin+tp8表格操作(1)----表头上方添加按钮和自定义按钮
buildAdmin 的表头上添加一些按钮,并实现功能 添加按钮 <template><!-- buttons 属性定义了 TableHeader 本身支持的顶部按钮,仅需传递按钮名即可 --><!-- 这里的框架自带的 顶部按钮 分别有 刷新 , 添加, 编辑&…...
MySQL 定时计划任务 事件的使用
目录 查看事件是否开启 开启事件 1)通过设置全局参数修改 2)更改配置文件 MySQL如何创建并执行事件? 例 1 MySQL查看事件状态信息 MySQL修改和删除事件 例 1 例 2 删除事件 例 3 在数据库管理中,经常要周期性的执行某…...
C++构造函数 拷贝构造函数 括号法显示法隐式转换法实现类
一.无参构造 & 有参构造 & 拷贝构造函数 拷贝的是自己所属的类,也就是克隆自己。 所以传参要穿自己的类名。 克隆归克隆,但是不能把本身给改了,所以参数前要加const。class Person { public:int age;public:Person(){cout<<&q…...
FreeRTOS中的内存分配策略
FreeRTOS为内存管理提供了几种不同的策略,分别由heap_1.c至heap_5.c实现。以下是每种策略: heap_1.c: 最简单的策略。只允许一次性的内存分配。不允许内存释放。对于只分配内存但不释放的系统特别有用,如仅在启动时分配任务和队列的系统。内存…...
HP惠普光影精灵7笔记本Victus by HP 16.1英寸游戏本16-d0000原装出厂Windows11.21H2预装OEM系统
下载链接:https://pan.baidu.com/s/1LGNeQR1AF1XBJb5kfZca5w?pwdhwk6 提取码:hwk6 可适用的型号: 16-d0111tx,16-d0112tx,16-d0125tx,16-d0127tx,16-d0128tx,16-d0129tx&#…...
组合模式 rust和java的实现
文章目录 组合模式介绍实现javarsut 组合模式 组合模式(Composite Pattern),又叫部分整体模式,是用于把一组相似的对象当作一个单一的对象。组合模式依据树形结构来组合对象,用来表示部分以及整体层次。这种类型的设计…...
大数据基础设施搭建 - MySQL
文章目录 一、检查是否安装过MySQL二、上传安装包三、安装MySQL3.1 安装mysql依赖3.2 安装mysql-client3.3 安装mysql-server 四、启动MySQL五、配置MySQL5.1 修改密码(1)查看密码(2)登陆(3)设置复杂密码&a…...
二叉树递归遍历
能帮到你的话,就给个赞吧 😘 二叉树遍历算法 指遍历一遍二叉树就能得到答案 什么是二叉树遍历 二叉树遍历 前中后序遍历 递归遍历 3种时间节点 递归遍历会依次遍历到每个节点。 而前中后序则是在递归遍历的基础上选择操作发生的时间。 递归遍历 …...
【ArcGIS Pro二次开发】:CC工具箱1.1.1更新_免费_安装即可用
CC工具箱1.1.1更新【2023.11.15】 使用环境要求:ArcGIS Pro 3.0 一、下载链接 工具安装文件及使用文档: https://pan.baidu.com/s/1OJmO6IPtMfX_vob3bMtvEg?pwduh5rhttps://pan.baidu.com/s/1OJmO6IPtMfX_vob3bMtvEg?pwduh5r 二、使用方法 1、在下…...
Dubbo的优雅下线原理分析
文/朱季谦 Dubbo如何实现优雅下线? 这个问题困扰了我一阵,既然有优雅下线这种说法,那么,是否有非优雅下线的说法呢? 这,还真有。 可以从linux进程关闭说起,其实,我们经常使用到杀…...
leetcode做题笔记2342. 数位和相等数对的最大和
给你一个下标从 0 开始的数组 nums ,数组中的元素都是 正 整数。请你选出两个下标 i 和 j(i ! j),且 nums[i] 的数位和 与 nums[j] 的数位和相等。 请你找出所有满足条件的下标 i 和 j ,找出并返回 nums[i] nums[j]…...
c# YOLOV5目标检测部署
using Emgu.CV; using Emgu.CV.CvEnum; using Emgu.CV.Dnn; using Emgu.CV.Structure; using Emgu.CV.Util...
学习笔记6——垃圾回收
学习笔记系列开头惯例发布一些寻亲消息 链接:https://baobeihuijia.com/bbhj/contents/3/190801.html java垃圾回收(stop the world) 专注于堆和方法区的垃圾回收,年轻代,老年代,永久代判断对象是否还存…...
3.1 Windows驱动开发:内核远程堆分配与销毁
在开始学习内核内存读写篇之前,我们先来实现一个简单的内存分配销毁堆的功能,在内核空间内用户依然可以动态的申请与销毁一段可控的堆空间,一般而言内核中提供了ZwAllocateVirtualMemory这个函数用于专门分配虚拟空间,而与之相对应…...
C++: 模板初阶
文章目录 一. 泛型编程二. 函数模板函数模板的原理函数模板的实例化隐式实例化: 让编译器根据实参推演模板参数的实际类型显示实例化: 在函数名后的<>中制定模板参数的世纪类型 模板参数的匹配原则 三. 类模板类模板的定义格式类模板的实例化 一. 泛型编程 如何实现一个…...
人工智能基础_机器学习036_多项式回归升维实战3_使用线性回归模型_对天猫双十一销量数据进行预测_拟合---人工智能工作笔记0076
首先我们拿到双十一从2009年到2018年的数据 可以看到上面是代码,我们自己去写一下 首先导包,和准备数据 from sklearn.linear_model import SGDRegressor import numpy as np import matplotlib.pyplot as plt X=np.arange(2009.2020)#左闭右开,2009到2019 获取从2009到202…...
【算法挨揍日记】day29——139. 单词拆分、467. 环绕字符串中唯一的子字符串
139. 单词拆分 139. 单词拆分 题目描述: 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 解题思路&am…...
YOLOv8-Seg改进:轻量级Backbone改进 | VanillaNet极简神经网络模型 | 华为诺亚2023
🚀🚀🚀本文改进:一种极简的神经网络模型 VanillaNet,支持vanillanet_5, vanillanet_6, vanillanet_7, vanillanet_8, vanillanet_9, vanillanet_10, vanillanet_11等版本,相比较yolov8-seg各个版本如下: layersparametersgradientsGFLOPsvanillanet_521230017523...
解决Requests中使用httpbin服务器问题:自定义URL的实现与验证
问题背景 在使用Python的Requests模块进行单元测试时,可能会遇到无法使用本地运行的httpbin服务器进行测试的问题。这是因为测试脚本允许通过环境变量HTTPBIN_URL指定用于测试的本地httpbin实例,但在某些测试用例中,URL是硬编码为httpbin.or…...
软考-高级-系统架构设计师教程(清华第2版)【第17章 通信系统架构设计理论与实践(P614~646)-思维导图】
软考-高级-系统架构设计师教程(清华第2版)【第17章 通信系统架构设计理论与实践(P614~646)-思维导图】 课本里章节里所有蓝色字体的思维导图...
【MATLAB源码-第82期】基于matlab的OFDM系统载波频移偏差(CFO)估计,对比三种不同的方法。
操作环境: MATLAB 2013b 1、算法描述 正交频分复用(OFDM)系统中的载波频率偏移(CFO)估计是一项关键技术,用于确保数据传输的准确性和效率。CFO通常由于振荡器频率不匹配和多普勒频移引起。不同的CFO估计…...
Docker Swarm: 容器编排的力量和优势深度解析
文章目录 Docker Swarm的核心概念1. 节点(Node)2. 服务(Service)3. 栈(Stack) 使用Docker Swarm1. 初始化Swarm2. 加入节点3. 创建服务4. 扩展和缩减服务5. 管理栈6. 管理服务更新 Docker Swarm的优势深度解…...
调整Windows键盘上只能看到拼音而无法看到实际的文本以及关闭输入法悬浮窗方法
一、输入法设置 如果您在键盘上只能看到拼音而无法看到实际的文本,这可能是因为您的输入法设置为中文拼音输入法或其他仅显示拼音的输入法。 要解决这个问题,您可以尝试以下方法: 1. 切换输入法:按下 Shift Alt 组合键或 Wind…...
【微软技术栈】C#.NET 中的管道操作
C#.NET 管道为进程间通信提供了平台。 管道分为两种类型: 匿名管道。 匿名管道在本地计算机上提供进程间通信。 与命名管道相比,虽然匿名管道需要的开销更少,但提供的服务有限。 匿名管道是单向的,不能通过网络使用。 仅支持一个服…...
Python学习笔记--进程
进程 Python 中的多线程其实并不是真正的多线程,如果想要充分地使用多核 CPU 的资源,在 Python 中大部分情况需要使用多进程。 Python 提供了非常好用的多进程包 multiprocessing,只需要定义一个函数,Python 会完成其他所有事情。 借助这个包,可以轻松完成从单进程到并…...
比亚迪刀片电池与特斯拉4680电池比较
1 电池材料 比亚迪刀片电池采用的磷酸铁锂LFP(LiFePO4),特斯拉的4680电池采用的三元锂。 磷酸铁锂:循环寿命长,安全性能好,价格低廉,但是能量密度低,导电性能差,低温表现…...
在写windows C++代码的时候,从代码安全角度考虑,我们应该注意什么?
在写windows C代码的时候,从代码安全角度考虑,我们应该注意什么?分别是:输入验证、内存管理、错误处理、并发和线程安全、使用安全的API、避免使用不安全的函数、最小权限原则。 一、输入验证 1. 用户输入验证 #include <io…...
【草料】uni-app ts vue 小程序 如何如何通过草料生成对应的模块化二维码
一、查看uni-app项目 1、找到路径 可以看到项目从 src-race-pages-group 这个使我们目标的查询页面 下面我们将这个路径copy到草料内 2、找到进入页面入参 一般我们都会选择 onload() 函数下的入参 这里我们参数的是 id 二、草料 建议看完这里的教程文档 十分清晰!…...
CMS与FullGC
JVM中的CMS(Concurrent Mark Sweep)GC和Full GC(Full Garbage Collection)是两种不同的垃圾回收算法。 CMS GC:CMS GC是一种并发的垃圾回收算法,它在运行期间与应用程序线程并发工作,尽可能减少…...
一款.NET开源的小巧、智能、免费的Windows内存清理工具 - WinMemoryCleaner
前言 我们在使用Windows系统的时候经常会遇到一些程序不会释放已分配的内存,从而导致电脑变得缓慢。今天给大家推荐一款.NET开源的小巧、智能、免费的Windows内存清理工具:WinMemoryCleaner。 使用Windows内存清理工具来优化内存,这样不必浪…...
iptables详解:链、表、表链关系、规则的基本使用
目录 防火墙基本概念 什么是防火墙? Netfilter与iptables的关系 链的概念 表的概念 表链关系 规则的概念 查询规则 添加规则 删除iptables中的记录 修改规则 更详细的命令(5链4表) 防火墙基本概念 什么是防火墙? 在…...
安全管理中心(设备和技术注解)
网络安全等级保护相关标准参考《GB/T 22239-2019 网络安全等级保护基本要求》和《GB/T 28448-2019 网络安全等级保护测评要求》 密码应用安全性相关标准参考《GB/T 39786-2021 信息系统密码应用基本要求》和《GM/T 0115-2021 信息系统密码应用测评要求》 1系统管理 1.1对系统管…...
Failed to execute org.scala-tools:maven-scala-plugin:2.15.2解决
原因也不是很清楚,查看一个博主文章(net.alchim31.maven:scala-maven-plugin:maven依赖无法下载或无法编译)得到的解决方案: 在idea的terminal执行以下语句即可实现maven对scala代码的编译: mvn clean scala:compile compile pac…...
C#中委托和事件的使用总结
委托(delegate)特别用于实现事件和回调方法。所有的委托(Delegate)都派生自 System.Delegate 类。事件是一种特殊的多播委托,仅可以从声明事件的类或结构中对其进行调用。类或对象可以通过事件向其他类或对象通知发生的…...
基于STM32的外部中断(EXTI)在嵌入式系统中的应用
外部中断(External Interrupt,EXTI)是STM32嵌入式系统中常见且重要的功能之一。它允许外部事件(例如按键按下、传感器触发等)通过适当的引脚触发中断,从而应用于各种嵌入式系统中。在STM32微控制器中&#…...
【心得】PHP的文件上传个人笔记
目录 1 php的文件上传绕过 黑名单绕过 2 php文件上传的00截断 3 iconv字符转换异常后造成了字符截断 4 文件后缀是白名单的时候的绕过 web服务器的解析漏洞绕过 5.高级文件上传绕过 1 .htaccess nginx.htaccess 2 服务端内容检测 3 配合伪协议来绕过 4.配合日志包含绕…...
深度学习之基于Pytorch和OCR的识别文本检测系统
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介深度学习与OCRPyTorch在OCR中的应用文本检测系统的关键组成部分1. 图像预处理2. 深度学习模型3. 文本检测算法4. 后处理 二、功能三、系统四. 总结 一项目简…...
三十一、W5100S/W5500+RP2040树莓派Pico<TCP_Server多路socket>
文章目录 1 前言2 简介2. 1 使用多路socket的优点2.2 多路socket数据交互原理2.3 多路socket应用场景 3 WIZnet以太网芯片4 多路socket设置示例概述以及使用4.1 流程图4.2 准备工作核心4.3 连接方式4.4 主要代码概述4.5 结果演示 5 注意事项6 相关链接 1 前言 W5100S/W5500是一…...
带你精通chrony服务器
华子目录 为什么会出现Chrony?Linux的两个时钟NTP介绍Chrony介绍安装与配置安装Chrony配置文件分析实验1实验2chronyc命令查看时间服务器chronyc sources输出分析其他命令 常见时区 为什么会出现Chrony? 由于IT系统中,准确的计时非常重要&am…...