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

AtCoder Beginner Contest 290 G. Edge Elimination(思维题 枚举+贪心)

题目

T(T<=100)组样例,每次给出一棵深度为d的k叉树,

其中,第i层深的节点个数为k^i(0\leq i \leq d), d \geq1,k \geq 2

保证k叉树的所有节点个数tot不超过1e18,

求在k叉树上构建一棵大小恰为x的连通块,所需要断开的最少的树边的条数(x<=tot<=1e18)

思路来源

乱搞AC

题解

其实不太知道为什么算个G题,可能是因为F题卡住了太多人

考虑连通块的点的lca位于哪一层,枚举lca所在层为第i层,

如果是第0层,不用切断,如果是第1层到第d层,需要先切断一条边,

只考虑第i层为根的这棵子树,若这棵子树不足x个点,可以直接跳过

否则,当前这棵子树总的点数一定大于x(等于x的情况直接break即可)

计当前还需要删的点的个数为sum2,当前删掉的边数为cur,

子树当前层的点为根及以下层点的总数为now,子树下一层的点为根及以下层的点数为nex

此刻,一定是优先断开靠上的边,靠上的一条边能直接削掉大小为nex的一棵子树

通过下取整确定削几棵,余数在下一层里考虑,直到要删的点为0或考虑到最后一层即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=65;
typedef long long ll;
int t,c;
ll d,k,x,a[N],sum[N],now,cur;
int main(){cin>>t;while(t--){cin>>d>>k>>x;a[0]=1;sum[0]=1;cur=0;for(int i=1;i<=d;++i){a[i]=1ll*a[i-1]*k;sum[i]=sum[i-1]+a[i];}ll ans=sum[d];for(int i=0;i<=d;++i){ll sum2=sum[i]-x,now=sum[i],cur=(i<d);if(sum2<0)continue;while(sum2>0){ll nex=(now-1)/k;cur+=sum2/nex;//printf("sum:%lld nex:%lld cur:%lld\n",sum,nex,cur);sum2%=nex;now=nex;}ans=min(ans,cur);}cout<<ans<<endl;}return 0;
} 

相关文章:

AtCoder Beginner Contest 290 G. Edge Elimination(思维题 枚举+贪心)

题目 T(T<100)组样例&#xff0c;每次给出一棵深度为d的k叉树&#xff0c; 其中&#xff0c;第i层深的节点个数为 保证k叉树的所有节点个数tot不超过1e18&#xff0c; 求在k叉树上构建一棵大小恰为x的连通块&#xff0c;所需要断开的最少的树边的条数(x<tot<1e18)…...

数据挖掘概述

目录1、数据挖掘概述2、数据挖掘常用库3、模型介绍3.1 分类3.2 聚类3.3 回归3.4 关联3.5 模型集成4、模型评估ROC 曲线5、模型应用1、数据挖掘概述 数据挖掘&#xff1a;寻找数据中隐含的知识并用于产生商业价值 数据挖掘产生原因&#xff1a;海量数据、维度众多、问题复杂 数…...

linux kernel iio 架构

linux kernel iio 架构讲解Linux IIO&#xff08;Industrial I/O&#xff09;架构是Linux内核提供的一种用于支持各种类型传感器和数据采集设备的子系统&#xff0c;包括温度、压力、湿度、加速度、光度等多种传感器。IIO架构的核心是一个通用的IIO子系统&#xff0c;它提供了一…...

Socket通信详解

Socket通信详解 文章目录Socket通信详解Socket流程介绍函数介绍编程实例Socket流程介绍 socket通信类似于电话通信&#xff0c;其服务器基本流程就是 Created with Raphal 2.3.0安装电话socket()分配电话号码bind()连接电话线listen()拿起话筒accept()函数介绍 socket() 其中…...

多分类、正则化问题

多分类问题 利用逻辑回归解决多分类问题&#xff0c;假如有一个训练集&#xff0c;有 3 个类别&#xff0c;分别为三角形 &#x1d466; 1&#xff0c;方框&#x1d466; 2&#xff0c;圆圈 &#x1d466; 3。我们下面要做的就是使用一个训练集&#xff0c;将其分成 3 个二…...

史上最全面的软件测试面试题总结(接口、自动化、性能全都有)

目录 思维发散 Linux 测试概念和模型 测试计划与工具 测试用例设计 Web项目 Python基础 算法 逻辑 接口测试 性能测试 总结感谢每一个认真阅读我文章的人&#xff01;&#xff01;&#xff01; 重点&#xff1a;配套学习资料和视频教学 思维发散 一个球&#xff…...

速来~与 Werner Vogels 博士一起探索敏捷性与创新速度一起提升的秘方

Amazon Web Services 的现代应用程序创新一直是 Amazon 公司坚持追求的核心目标。约20年前&#xff0c;我们经历了一次彻底的转型&#xff0c;旨在建立起“发明、发布、再发明、再发布、重新开始、洗牌、再重复”的快速迭代流程。正是此番探索&#xff0c;彻底改变了我们构建应…...

Apache Hadoop、HDFS介绍

目录Hadoop介绍Hadoop集群HDFS分布式文件系统基础文件系统与分布式文件系统HDFS简介HDFS shell命令行HDFS工作流程与机制HDFS集群角色与职责HDFS写数据流程&#xff08;上传文件&#xff09;HDFS读数据流程&#xff08;下载文件&#xff09;Hadoop介绍 用Java语言实现开源 允许…...

python“r e 模块“常见函数详解

正则表达式&#xff1a;英文Regular Expression,是计算机科学的一个重要概念&#xff0c;她使用一种数学算法来解决计算机程序中的文本检索&#xff0c;匹配等问题&#xff0c;正则表达式语言是一种专门用于字符串处理的语言。在很多语言中都提供了对它的支持&#xff0c;re模块…...

【数据结构】二叉树的四种遍历方式——必做题

写在前面学完上一篇文章的二叉树的遍历之后&#xff0c;来尝试下面的习题吧开始做题144. 二叉树的前序遍历 - 力扣&#xff08;LeetCode&#xff09;94. 二叉树的中序遍历 - 力扣&#xff08;LeetCode&#xff09;145. 二叉树的后序遍历 - 力扣&#xff08;LeetCode&#xff09…...

Nginx使用“逻辑与”配置origin限制,修复CORS跨域漏洞

目录1.漏洞报告2.漏洞复现3.Nginx 修复3.1 添加请求头3.2 配置origin限制2.3 调整origin限制1.漏洞报告 漏洞名称&#xff1a; CORS 跨域漏洞等级&#xff1a; 中危漏洞证明&#xff1a; Origin从任何域名都可成功访问&#xff0c;未做任何限制。漏洞危害&#xff1a; 因为同源…...

Laravel框架02:路由与控制器

Laravel框架02&#xff1a;路由与控制器一、路由配置文件二、路由参数三、路由别名四、路由群组五、控制器概述六、控制器路由七、接收用户输入一、路由配置文件 以web网页路由文件为例&#xff1a; 默认根路由 路由定义格式Route::请求方式(请求的URL, 匿名函数或控制响应的方…...

【POJ 2418】Hardwood Species 题解(映射)

描述 阔叶树是一种植物群&#xff0c;具有宽阔的叶子&#xff0c;结出果实或坚果&#xff0c;通常在冬天休眠。 美国的温带气候造就了数百种阔叶树种的森林&#xff0c;这些树种具有某些生物特征。例如&#xff0c;虽然橡树、枫树和樱桃都是硬木树&#xff0c;但它们是不同的物…...

React组件之间的通信方式总结(下)

一、写一个时钟 用 react 写一个每秒都可以更新一次的时钟 import React from react import ReactDOM from react-domfunction tick() {let ele <h1>{ new Date().toLocaleTimeString() }</h1>// Objects are not valid as a React child (found: Sun Aug 04 20…...

【RabbitMQ笔记07】消息队列RabbitMQ七种模式之Publisher Confirms发布确认模式

这篇文章&#xff0c;主要接收消息队列RabbitMQ七种模式之Publisher Confirms发布确认模式。 目录 一、消息队列 1.1、发布确认模式 1.2、案例代码 &#xff08;1&#xff09;引入依赖 &#xff08;2&#xff09;编写生产者【消息确认--单条确认】 &#xff08;3&#xf…...

【华为OD机试模拟题】用 C++ 实现 - IPv4 地址转换成整数(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 去重求和(2023.Q1) 文章目录 最近更新的博客使用说明IPv4 地址转换成整数题目输入输出示例一输入输出说明示例一输入输出说明Code使用说明 参加华为od机试,一定要注意不要完全背诵代码,需要理解之后模仿写出,...

闭包与高阶函数

文中内容均来自于曾探《JavaScript设计模式与开发实践》的学习笔记。闭包作用域变量的作用域&#xff0c;就是指变量的有效范围。局部变量、全局变量。变量的搜索是从内到外而非从外到内的。变量的生命周期对于全局变量莱索&#xff0c;全局变量的生命周期是永久的&#xff0c;…...

人工智能轨道交通行业周刊-第35期(2023.2.20-2.26)

本期关键词&#xff1a;重庆智慧轨道、智能运维主机、标准轨距、地方铁路公报、景深、机器视觉应用 1 整理涉及公众号名单 1.1 行业类 RT轨道交通人民铁道世界轨道交通资讯网铁路信号技术交流北京铁路轨道交通网上榜铁路视点ITS World轨道交通联盟VSTR铁路与城市轨道交通Rai…...

快慢指针判断链表是否有环

快慢指针判断链表是否有环 单链表有可能存在环&#xff0c;有些情况下要判断一个单链表是否有环。数组的有个快慢指针的方法&#xff0c;其实单链表和数组有相似的地方&#xff0c;可以使用快慢指针的方法。具体做法如下&#xff1a; 首先创建两个指针&#xff0c;它们初始时…...

《MongoDB入门教程》第26篇 聚合统计之$max/$min表达式

本文将会介绍两个 MongoDB 表达式&#xff0c;返回一组数据中最大值的 $max 表达式&#xff0c;以及返回一组数据中最小值的 $min 表达式。 $max 表达式 $max 表达式用于返回一组数据中的最大值&#xff0c;语法如下&#xff1a; { $max: <expression> }$max 表达式在…...

FPGA纯verilog解码SDI视频 纯逻辑资源实现 提供2套工程源码和技术支持

目录1、前言2、硬件电路解析SDI摄像头Gv8601a单端转差GTX解串SDI解码VGA时序恢复YUV转RGB图像输出FDMA图像缓存HDMI输出3、工程1详解&#xff1a;无缓存输出4、工程2详解&#xff1a;缓存3帧输出5、上板调试验证并演示6、福利&#xff1a;工程代码的获取1、前言 FPGA实现SDI视…...

JVM篇之垃圾回收

一.如何判断对象可以回收 1.引用计数法 只要一个对象被其他变量所引用&#xff0c;就让它的计数加1&#xff0c;被引用了两次就让它的计数变成2&#xff0c;当这个变量的计数变成0时&#xff0c;就可以被垃圾回收&#xff1b; 弊端&#xff1a;当出现如下图的情况&#xff0…...

尝试用程序计算Π(3.141592653......)

文章目录1. π\piπ2. 用微积分来计算π\piπ2.1 原理2.2 代码2.3 结果2.4 分析1. π\piπ π\piπ的重要性或者地位不用多说&#xff0c;有时候还是很好奇&#xff0c;精确地π\piπ值是怎么计算出来的。研究π\piπ的精确计算应该是很多数学家计算机科学家努力的方向&#xf…...

【异常检测三件套】系列3--时序异常检测综述

写在前面: 异常检测共包含3个内容,从多个方面剖析异常检测方法,本文为第三篇。过往内容请查看以下链接: 【异常检测三件套】系列1--14种异常检测算法https://blog.csdn.net/allein_STR/article/details/128114175?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%…...

关于SAP 错误日志解析

有时候启动或操作sap会出现故障&#xff0c;只是察看sap用户当前目录下的日志文件可能不得要领&#xff0c;此时有必要察看work目录下的一些trace. 以Linux系统为例&#xff0c;其他的也差不多。 instance说明 如下 DVEBMGS?? ABAP Central Instance D?? …...

java:自定义变量加载到系统变量后替换shell模版并执行shell

这里的需求前提是&#xff0c;在项目中进行某些操作前&#xff0c;需要在命令后对shell配置文件的进行修改&#xff08;如ip、port&#xff09;&#xff0c;这个对于用户是不友好的&#xff0c;需要改为用户页面输入ip、port&#xff0c;后台自动去操作修改配置&#xff1b;那么…...

Redis高级删除策略与数据淘汰

第二章&#xff1a;Redis高级 学习目标 目标1&#xff1a;能够说出redis中的数据删除策与略淘汰策略 目标2&#xff1a;能够说出主从复制的概念&#xff0c;工作流程以及场景问题及解决方案 目标3&#xff1a;能够说出哨兵的作用以及工作原理&#xff0c;以及如何启用哨兵 …...

社畜大学生的Python之pandas学习笔记,保姆入门级教学

接上期&#xff0c;上篇介绍了 NumPy&#xff0c;本篇介绍 pandas。 目录 pandas 入门pandas 的数据结构介绍基本功能汇总和计算描述统计处理缺失数据层次化索引 pandas 入门 Pandas 是基于 Numpy 构建的&#xff0c;让以 NumPy 为中心的应用变的更加简单。 Pandas是基于Numpy…...

20_FreeRTOS低功耗模式

目录 低功耗模式简介 STM32低功耗模式 Tickless模式详解 Tickless模式相关配置 实验源码 低功耗模式简介 很多应用场合对于功耗的要求很严格,比如可穿戴低功耗产品、物联网低功耗产品等。 一般MCU都有相应的低功耗模式,裸机开发时可以使用MCU的低功耗模式。 FreeRTOS也…...

Hive的使用方式

操作Hive可以在Shell命令行下操作&#xff0c;或者是使用JDBC代码的方式操作 针对命令行这种方式&#xff0c;其实还有两种使用 第一个是使用bin目录下的hive命令&#xff0c;这个是从hive一开始就支持的使用方式 后来又出现一个beeline命令&#xff0c;它是通过HiveServer2服…...