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

【二分+贪心】CF1665 C

Problem - C - Codeforces

题意:

 

思路:

一开始想太简单wa6了

只想到先感染大的分量,然后最后把最大的分量剩下的染色

但是可能会有别的分量更大(因为最后给最大的染色之后可能不再是最大的)

可以用堆维护,但是这里用二分做法

我们可以二分答案mid,问题就变成了mid秒内能否感染所有结点.

首先Injection一定用于优先感染兄弟结点比较多的结点,这样可以充分利用Spreading,我们可以结点按照兄弟的数量排序,然后优先感染兄弟多的结点.这样我们就知道了,第一秒被Injection的结点剩下的时间里可以被Spreading mid-1个兄弟,第二秒可以被Injection的结点可以被Spreading mid-2个兄弟,所以我们扫描一遍就可以知道还剩下多少个兄弟结点还没被感染,判断能否用剩下的Injection的操作将这些结点感染即可. 

Code:

#include <bits/stdc++.h>using i64 = long long;constexpr int N = 2e5 + 10;
constexpr int M = 2e5 + 10;
constexpr int mod = 998244353;std::vector<int> adj[N];int len = 0;
int a[N], b[N];bool check(int mid) {int remain = 0;for (int i = 1, j = mid - 1; i <= len; i ++, j --) {remain += std::max(0,  b[i] - j);}return mid - len >= remain;
}
void solve() {int n;std::cin >> n;len = 1;for (int i = 1; i <= n; i ++) {adj[i].clear();b[i] = 0;}b[0] = 1;for (int i = 2; i <= n; i ++) {int x;std::cin >> x;adj[x].push_back(i);}for (int i = 1; i <= n; i ++) {if (adj[i].size()) {b[++len] = adj[i].size() - 1;}}std::sort(b + 1, b + 1 + len, std::greater<int>());int ans = 0;int l = 1, r = 1e9;while(l <= r) {int mid = l + r >> 1;if (check(mid)) {ans = mid;r = mid - 1;}else {l = mid + 1;}}std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}

相关文章:

【二分+贪心】CF1665 C

Problem - C - Codeforces 题意&#xff1a; 思路&#xff1a; 一开始想太简单wa6了 只想到先感染大的分量&#xff0c;然后最后把最大的分量剩下的染色 但是可能会有别的分量更大&#xff08;因为最后给最大的染色之后可能不再是最大的&#xff09; 可以用堆维护&#xf…...

【Wamp】安装 | 局域网内设备访问

安装教程&#xff1a; https://wampserver.site/article/1.html 下载 https://www.wampserver.com/en/ 安装路径上不能有中文 安装好之后图标呈绿色 放入网页文件 将网页文件放置于wamp文件夹的www子文件夹 例如&#xff1a;\Wamp\program\www 修改http端口 WAMP服务器…...

【golang】类型推断和变量重声明

类型推断是一种编程语言在编译期自动解释表达式类型的能力。 1.Go语言的类型推断可以带来哪些好处&#xff1f; 在写代码时&#xff0c;我们通过使用Go语言的类型推断会节省敲击次数&#xff0c;而节省下来的键盘敲击次数几乎可以忽略不记。但它真正的好处&#xff0c;往往会…...

“算法详解”系列第3卷贪心算法和动态规划出版

“算法详解”系列图书共有4卷&#xff0c;目前1到3卷已经出版。最新出版的是第3卷—贪心算法和动态规划。 算法详解 卷3 贪心算法和动态规划 “算法详解”系列图书共有4卷&#xff0c;本书是第3卷—贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、集群、哈夫曼编…...

CSS前端开发指南:创造精美的用户界面

简介&#xff1a; 《CSS前端开发指南&#xff1a;创造精美的用户界面》是一本旨在帮助读者掌握CSS技术&#xff0c;实现令人惊叹的前端用户界面的实用指南。无论您是初学者还是有经验的开发者&#xff0c;本书都将为您提供全面的知识和实用技巧&#xff0c;帮助您创建引人注目…...

代数学与理论物理中常见的群

代数学与理论物理中常见的群 代数学与理论物理中常见的群 四阶群 六阶群 对称群 二维转动群 三维转动群 三维正交群 群 O3群...

解析xml文件,获取需要的数据并写入txt文件中

_ 话不多说&#xff01;直接上代码&#xff01;_ 1、XmlUtil.java xml解析工具类 public class XmlUtil {private static String dicName "";private static String dicValue "";// 用于存储需要的数据private static List<Map<String, Str…...

JavaScript基础 第三天

1.for循环 2.数组的基本使用和操作 3.数组排序 一.for循环 ① 语法&#xff1a;把声明起始值&#xff0c;循环条件&#xff0c;变量值写到一起&#xff0c;让人一目了然 for(变量起始值;终止条件;变量变化量) {// 循环体 }举例&#xff1a; for (let i 0; i < 100; i)…...

2.Redis部署到Windows服务器

1.下载安装包 Redis官网没有提供Windows的安装包&#xff0c;可以去gitHub或者网上去下载Redis的Windows安装包。 2.Redis部署到服务器 将Redis整个文件夹放到服务器的指令目录&#xff0c;然后进行修改Redis的配置文件 redis.windows.conf&#xff0c;修改里面的配置项 1.b…...

【修正-高斯拉普拉斯滤波器-用于平滑和去噪】基于修正高斯滤波拉普拉斯地震到达时间自动检测研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Go语言基础: 有参函数Func、Map、Strings详细案例教程

目录标题 一、Variadic Functions1.Syntax2.Examples and understanding how variadic functions work3.Slice arguments vs Variadic arguments 仅改变可变参数4.Gotcha 二、Map1.Create a Map2.Retrieving value for a key from a map3.Checking if a key exists4.Iterate ov…...

JDBC连接数据库如何实现你会吗???

1.首先建立一个maven项目。。。详细过程来了哇 还没有安装maven的童鞋可以看这里&#xff1a;maven的下载安装与配置环境变量&#xff01;&#xff01;&#xff01;&#xff08;全网最详细&#xff09;_明天更新的博客-CSDN博客 有很多小伙伴就有疑问啦&#xff0c;难道我直接…...

C#与C++交互(2)——ANSI、UTF8、Unicode文本编码

【前言】 我们知道计算机上只会存储二进制的数据&#xff0c;无论文本、图片、音频、视频等&#xff0c;当我们将其保存在计算机上时&#xff0c;都会被转成二进制的。我们打开查看的时候&#xff0c;二进制数据又被转成我们看得懂的信息。如何将计算机上的二进制数据转为我们…...

SQLSTATE[42000]: this is incompatible with sql_mode=only_full_group_by in

执行 SELECT *FROM test WHERE id>1 GROUP BY name having AVG(age)>10 ORDER BY id desc limit 1 提示错误 Fatal error: Uncaught PDOException: SQLSTATE[42000]: Syntax error or access violation: 1055 Expression #1 of SELECT list is not in GROUP BY clause…...

企业权限管理(五)-订单分页

订单分页查询 PageHelper介绍 PageHelper是国内非常优秀的一款开源的mybatis分页插件&#xff0c;它支持基本主流与常用的数据库&#xff0c;例如mysql、oracle、mariaDB、DB2、SQLite、Hsqldb等。 PageHelper使用 集成 引入分页插件有下面2种方式&#xff0c;推荐使用 Maven …...

Blender如何给fbx模型添加材质贴图并导出带有材质贴图的模型

推荐&#xff1a;使用 NSDT场景编辑器快速助你搭建可二次编辑的3D应用场景 此教程适合新手用户&#xff0c;专业人士直接可直接绕路。 本教程中介绍了利用Blender建模软件&#xff0c;只需要简单几步就可以为模型添加材质贴&#xff0c;图&#xff0c;并且导出带有材质的模型文…...

MySQL不走索引的情况分析

未建立索引 当数据表没有设计相关索引时&#xff0c;查询会扫描全表。 create table test_temp (test_id int auto_incrementprimary key,field_1 varchar(20) null,field_2 varchar(20) null,field_3 bigint null,create_date date null );expl…...

安装ubuntu22.04系统,配置国内源以及ssh远程登录

一、安装ubuntu22.04系统 原文连接&#xff1a;Ubuntu操作系统22.04版本安装教程-VMware虚拟机_wx63f86e949a470的技术博客_51CTO博客 1.点击界面左侧的开启此虚拟机&#xff0c;即可进入Ubuntu操作系统安装界面&#xff0c;点击​​Try or Install Ubuntu ​​即可开始安装 …...

win10 安装ubuntu子系统并安装宝塔

1、安装子系统 2、ubuntu 中安装宝塔 这里需要注意的&#xff1a; 大部分文章上写的是“面板账户登录信息”不能直接访问&#xff0c;要改成127.0.0.1&#xff1a;8888去访问。 这种情况适合“面板账户登录信息”端口就是8888。 想我的就是32757 这时你就要用 http://127.0.0…...

gazebo 导入从blender导出的dae等文件

背景&#xff1a; gazebo 模型库里的模型在我需要完成的任务中不够用&#xff0c;还是得从 solidworks、3DMax, blender这种建模软件里面在手动画一些&#xff0c;或者去他们的库里面在挖一挖。 目录 1 blender 1-1 blender 相关links 1-2 install 2 gazebo导入模型 2-1 g…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...