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

【颜色平衡树 / E】

题目

思路

  • DFS暴力 60分

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
const int M = 5010;
int h[N], e[M], ne[M], idx;
int c[N], f;
int ans;
void add(int a, int b)  // 添加一条边a->b
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool check(int tmp[])
{int last = 0;for(int i = 1; i <= 5000; i++){if(!last && tmp[i]) last = tmp[i];else if(last && tmp[i]){if(last != tmp[i]) return false;last = tmp[i];}}return true;
}
void dfs(int u, int f[])
{int tmp[N] = {0};//根节点颜色算进子树tmp[c[u]] += 1;bool leaf = true;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];dfs(j, tmp);leaf = false;}//判断平衡性if(leaf) ans++;else{if(check(tmp)) ans++;}//呈递颜色for(int i = 1; i <= 5000; i++)f[i] += tmp[i];
}
int main()
{int n;cin >> n;memset(h, -1, sizeof h);for(int i = 1; i <= n; i++){cin >> c[i] >> f;add(f, i);}int tmp[N] = {0};dfs(1, tmp);cout << ans;
}

相关文章:

【颜色平衡树 / E】

题目 思路 DFS暴力 60分 代码 #include <bits/stdc.h> using namespace std; const int N 5010; const int M 5010; int h[N], e[M], ne[M], idx; int c[N], f; int ans; void add(int a, int b) // 添加一条边a->b {e[idx] b, ne[idx] h[a], h[a] idx ; } …...

滑动窗口--(中篇)

将X减到0的最小操作数 给你一个整数数组 nums 和一个整数 x 。每一次操作时&#xff0c;你应当移除数组 nums 最左边或最右边的元素&#xff0c;然后从 x 中减去该元素的值。请注意&#xff0c;需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 &#xff0c;返…...

Java性能调优:实战技巧与最佳实践

引言 Java作为企业级应用开发的首选语言之一&#xff0c;其性能直接影响到系统的响应速度和用户体验。性能调优是一项复杂的工作&#xff0c;涉及多个层面的知识和技术。本文将通过具体的示例&#xff0c;探讨一些常见的性能调优技巧及最佳实践。 1. 了解你的应用程序 示例&…...

排版套料系统设计说明

先上效果图 项目地址 1.产品介绍 产品名称&#xff1a;StreamFit 智能排版套料系统 主要功能&#xff1a; 智能排版优化 功能描述&#xff1a;StreamFit 利用先进的算法技术&#xff0c;自动对各类材料&#xff08;如布料、金属板材、纸张等&#xff09;进行高效排版布局&am…...

算法修炼之路之二分查找

目录 一:三大二分介绍及模板 1.普通二分 2.查找左右边界的二分及模板 二:LeetCode OJ练习 1.第一题 2.第二题 3.第三题 4.第四题 5.第五题 6.第六题 一:三大二分介绍及模板 1.普通二分 这里通过一道题来引出普通二分及模板 LeetCode_704 二分查找 画图分析: 具体代…...

OpenAI预计明年将推出“代理”系统

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

每日OJ题_牛客_重排字符串_贪心_C++_Java

目录 牛客_重排字符串_贪心 题目解析 C代码 Java代码 牛客_重排字符串_贪心 重排字符串 (nowcoder.com) 描述&#xff1a; 小红拿到了一个只由小写字母组成的字符串。她准备把这个字符串重排&#xff08;只改变字母的顺序&#xff0c;不改变数量&#xff09; …...

Python 进阶部分详细整理

1. 面向对象编程&#xff08;OOP&#xff09; 面向对象编程 (OOP) 是一种通过将程序中的数据和功能封装为对象的编程范式。OOP 基于四个核心概念&#xff1a;类与对象、继承、封装与多态。 类与对象 类&#xff08;Class&#xff09;&#xff1a;类是创建对象的蓝图或模板。它…...

[ RK3566-Android11 ] 关于移植 RK628F 驱动以及后HDMI-IN图像延迟/无声等问题

问题描述 由前一篇文章https://blog.csdn.net/jay547063443/article/details/142059700?fromshareblogdetail&sharetypeblogdetail&sharerId142059700&sharereferPC&sharesourcejay547063443&sharefromfrom_link&#xff0c;移植HDMI-IN部分驱动后出现&a…...

【黑马点评】 使用RabbitMQ实现消息队列——2.使用RabbitMQ监听秒杀下单

2 使用RabbitMQ实现消息队列 2.1 修改\hm-dianping\pom.xmlpom.xml文件 添加RabbitMQ的环境 <!-- RabbitMQ--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </depe…...

业务封装与映射 -- OTUk/ODUk/OPUk开销帧结构

开销是为了保证净荷正常、灵活传送所必须附加的供网络运行、管理和维护&#xff08;OAM&#xff09;使用的字节。 OTN电层开销包括OTUk开销、ODUk开销、OPUk开销、OTUCn开销、ODUCn开销、OPUCn开销和帧对齐开销。 SM开销属于OTU开销&#xff0c;占用3个字节&#xff1b;PM开销…...

Vim基本用法

Vim用法 一、基本模式 1. 普通模式&#xff08;Normal Mode&#xff09; 移动光标 基本移动&#xff1a;使用方向键&#xff08;h左移、j下移、k上移、l右移&#xff09;&#xff0c;也可以使用 H&#xff08;移到屏幕顶部&#xff09;、M&#xff08;移到屏幕中间&#xff…...

python 实现Tarjan 用于在有向图中查找强连通分量的算法

Tarjan 用于在有向图中查找强连通分量的算法介绍 Tarjan算法是一种用于在有向图中查找强连通分量的高效算法&#xff0c;由Robert Tarjan在1972年提出。强连通分量是指在有向图中&#xff0c;如果从顶点u到顶点v以及从顶点v到顶点u都存在一条路径&#xff0c;那么顶点u和顶点v…...

Qt开发技巧(十五)字符串去除空格,跨网段搜索不生效,设置图片显示失败问题,表格视图的批量删除,主动判断字串编码,开启向前查询的属性,画家类载入html来绘制

继续讲一些Qt开发中的技巧操作&#xff1a; 1.字符串去除空格 我们经常会遇到字符串重去除空格的情况&#xff0c;对于QString去除空格&#xff0c;有多种场景&#xff0c;可能需要去除左侧、右侧、所有等位置的空格&#xff1b; //字符串去空格 -1移除左侧空格 0移除所有空格…...

【机器学习】智驭未来:探索机器学习在食品生产中的革新之路

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀目录 &#x1f50d;1. 引言&#xff1a;探索机器学习在食品生产中的革新之路&#x1f4d2;2. 机器学习在食品质量控制中的应用&#x1f31e;实…...

Ubuntu 安装CUDA并使用Docker配置Pytorch环境

文章目录 参考安装顺序Nvidia GPU driverDockerNvidia Container ToolkitDocker PyTorch 1. Nvidia GPU Driver2. Docker 安装&#xff08;使用apt存储库进行安装&#xff09;3. Nvidia Container Toolkit3.1 Docker测试GPU 参考 安装顺序 Nvidia GPU driver Docker Nvidia…...

【论文阅读】Simulating 500 million years of evolution with a language model

Simulating 500 million years of evolution with a language model 1、概述 展示了语言模型在蛋白质设计和进化模拟方面的能力。通过对 ESM3 模型的研究,发现其能够生成与自然蛋白质差异较大且具有功能的新蛋白质,如新型绿色荧光蛋白(GFP),表明语言模型可以达到自然进化…...

detectron2/layers源码笔记

from .wrappers import ( BatchNorm2d, Conv2d, #在torch.conv2d的基础上集成了norm层和activation层 ConvTranspose2d, cat, interpolate, Linear, nonzero_tuple, #nonzero_tuple(x)得到tuple of 每个维度的索引 cross_entropy, empty_input_loss_func…...

LLM+知识图谱新工具! iText2KG:使用大型语言模型构建增量知识图谱

iText2KG是一个基于大型语言模型的增量知识图谱构建工具&#xff0c;通过从文本文档中提取实体和关系来逐步构建知识图谱。该工具具有零样本学习能力&#xff0c;能够在无需特定训练的情况下&#xff0c;在多个领域中进行知识提取。它包括文档提炼、实体提取和关系提取模块&…...

React基础-快速梳理

React介绍 React由Meta公司开发&#xff0c;是一个用于构建Web和原生交互界面的库 React的优势 相较于传统基于DOM开发的优势 组件化的开发方式不错的性能 相较于其它前端框架的优势 丰富的生态跨平台支持 开发环境创建 create-react-app是一个快速创建React开发环境的…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...