当前位置: 首页 > news >正文

小美的树上染色

美团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届秋招笔试第一场编程真题 先提一个小知识&#xff1a;题目中凡是提到树结构都要使用图的存储方式&#xff0c;只有二叉树例外。 分析&#xff1a;在树结构中&#xff0c;孩子和父节点是相邻节点&#xff0c;而父节点可能有多个孩子节点。在染色的过程中&#xff0c;…...

1.rk3588的yolov5运行:pt_onnx_rknn转换及rknn在rk3588系统python运行

自己有点笨&#xff0c;查资料查了一周才完美的实现了yolov5在rk3588环境下的运行&#xff0c;在这里写具体步骤希望大家少走弯路。具体步骤如下&#xff1a; 一、yolov5的原代码下载及pt文件转换为onnx文件 1.yolov5的原代码下载及环境搭建 在这里一定要下载正确版本的源代码…...

适用于全部安卓手机的 5 大免费 Android 数据恢复

您是否面临这样一种情况&#xff0c;即在Android设备上丢失了一些重要文件&#xff0c;但不知道应该选择哪种Android数据恢复来取回它们&#xff1f; 如果您以前从未备份过Android数据&#xff0c;则很难解决问题。 本文将介绍排名前5位的免费Android数据恢复软件。 您可以获…...

【案例分享】BenchmarkSQL 5.0 压测 openGauss 5.0.0

一、前言 本次BenchmarkSQL 压测openGauss仅作为学习使用压测工具测试tpcc为目的&#xff0c;并不代表数据库性能如本次压测所得数据。实际生产性能压测&#xff0c;还需结合服务器软硬件配置、数据库性能参数调优、BenchmarkSQL 配置文件参数相结合&#xff0c;是一个复杂的过…...

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路径下&#xff0c;新建文件夹themes文件夹&#xff0c;用terminal新建也可以。 使用file editor上传文件 使用Terminal解压 mkdir themes unzip home-assistan…...

《2020年最新面经》—字节跳动Java社招面试题

文章目录 前言&#xff1a;一面&#xff1a;01、Java基础知识答疑&#xff0c;简单概述一下&#xff1f;02、倒排索引了解吗&#xff1f;使用Java语言怎么实现倒排&#xff1f;03、详细讲解一下redis里面的哈希表&#xff0c;常用的Redis哈希表命名有哪些&#xff0c;举例说明其…...

2.3IP详解及配置

2.3IP详解及配置 一、ip地址组成 IP地址由4部分数字组成&#xff0c;每部分数字对应于8位二进制数字&#xff0c;各部分之间用小数点分开 这是点分 2进制 如果换算为10进制我们称为点分10进制. 每个ip地址由两部分组成网络地址(NetID)和主z机地址(HostID).网络地址表示其属于…...

Python程序打包指南:手把手教你一步步完成

最近感兴趣想将开发的项目转成Package&#xff0c;研究了一下相关文章&#xff0c;并且自己跑通了&#xff0c;走了一下弯路&#xff0c;这里记录一下如何打包一个简单的Python项目&#xff0c;展示如何添加必要的文件和结构来创建包&#xff0c;如何构建包&#xff0c;以及如何…...

Linux yum 使用时提示 获取 GPG 密钥失败Couldn‘t open file RPM-GPG-KEY-EPEL-7

资料 错误提示&#xff1a; no crontab for root - using an empty one 888 原因剖析&#xff1a; 第一次使用crontab -e 命令时会让我们选择编辑器&#xff0c;很多人会不小心选择默认的nano&#xff08;不好用&#xff09;&#xff0c;或则提示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 的表头上添加一些按钮&#xff0c;并实现功能 添加按钮 <template><!-- buttons 属性定义了 TableHeader 本身支持的顶部按钮&#xff0c;仅需传递按钮名即可 --><!-- 这里的框架自带的 顶部按钮 分别有 刷新 &#xff0c; 添加&#xff0c; 编辑&…...

MySQL 定时计划任务 事件的使用

目录 查看事件是否开启 开启事件 1&#xff09;通过设置全局参数修改 2&#xff09;更改配置文件 MySQL如何创建并执行事件&#xff1f; 例 1 MySQL查看事件状态信息 MySQL修改和删除事件 例 1 例 2 删除事件 例 3 在数据库管理中&#xff0c;经常要周期性的执行某…...

C++构造函数 拷贝构造函数 括号法显示法隐式转换法实现类

一.无参构造 & 有参构造 & 拷贝构造函数 拷贝的是自己所属的类&#xff0c;也就是克隆自己。 所以传参要穿自己的类名。 克隆归克隆&#xff0c;但是不能把本身给改了&#xff0c;所以参数前要加const。class Person { public:int age;public:Person(){cout<<&q…...

FreeRTOS中的内存分配策略

FreeRTOS为内存管理提供了几种不同的策略&#xff0c;分别由heap_1.c至heap_5.c实现。以下是每种策略&#xff1a; heap_1.c: 最简单的策略。只允许一次性的内存分配。不允许内存释放。对于只分配内存但不释放的系统特别有用&#xff0c;如仅在启动时分配任务和队列的系统。内存…...

HP惠普光影精灵7笔记本Victus by HP 16.1英寸游戏本16-d0000原装出厂Windows11.21H2预装OEM系统

下载链接&#xff1a;https://pan.baidu.com/s/1LGNeQR1AF1XBJb5kfZca5w?pwdhwk6 提取码&#xff1a;hwk6 可适用的型号&#xff1a; 16-d0111tx&#xff0c;16-d0112tx&#xff0c;16-d0125tx&#xff0c;16-d0127tx&#xff0c;16-d0128tx&#xff0c;16-d0129tx&#…...

组合模式 rust和java的实现

文章目录 组合模式介绍实现javarsut 组合模式 组合模式&#xff08;Composite Pattern&#xff09;&#xff0c;又叫部分整体模式&#xff0c;是用于把一组相似的对象当作一个单一的对象。组合模式依据树形结构来组合对象&#xff0c;用来表示部分以及整体层次。这种类型的设计…...

大数据基础设施搭建 - MySQL

文章目录 一、检查是否安装过MySQL二、上传安装包三、安装MySQL3.1 安装mysql依赖3.2 安装mysql-client3.3 安装mysql-server 四、启动MySQL五、配置MySQL5.1 修改密码&#xff08;1&#xff09;查看密码&#xff08;2&#xff09;登陆&#xff08;3&#xff09;设置复杂密码&a…...

二叉树递归遍历

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 二叉树遍历算法 指遍历一遍二叉树就能得到答案 什么是二叉树遍历 二叉树遍历 前中后序遍历 递归遍历 3种时间节点 递归遍历会依次遍历到每个节点。 而前中后序则是在递归遍历的基础上选择操作发生的时间。 递归遍历 …...

【ArcGIS Pro二次开发】:CC工具箱1.1.1更新_免费_安装即可用

CC工具箱1.1.1更新【2023.11.15】 使用环境要求&#xff1a;ArcGIS Pro 3.0 一、下载链接 工具安装文件及使用文档&#xff1a; https://pan.baidu.com/s/1OJmO6IPtMfX_vob3bMtvEg?pwduh5rhttps://pan.baidu.com/s/1OJmO6IPtMfX_vob3bMtvEg?pwduh5r 二、使用方法 1、在下…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...