当前位置: 首页 > 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…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析

1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器&#xff08;TI&#xff09;推出的一款 汽车级同步降压转换器&#xff08;DC-DC开关稳压器&#xff09;&#xff0c;属于高性能电源管理芯片。核心特性包括&#xff1a; 输入电压范围&#xff1a;2.95V–6V&#xff0c;输…...