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

【省选模拟测试23 T1直径】更好的做法

题目大意和普通做法

省选模拟测试23 T1直径


题解

对于上文中有三个儿子的根节点的树,其直径数量为ab+bc+caab+bc+caab+bc+ca。那么对于上文中有nnn个儿子的根节点的树,其直径数量为多少呢?

每个儿子所在子树中的点与其他儿子所在子树中的点都能组成一次直径,而两个点都能组成一次直径,所以要除以2。设第iii个儿子的儿子数量为aia_iai,则直径数量为

(∑ai)2−∑ai22\dfrac{(\sum a_i)^2-\sum a_i^2}{2}2(ai)2ai2

要让k=(∑ai)2−∑ai22k=\dfrac{(\sum a_i)^2-\sum a_i^2}{2}k=2(ai)2ai2,即2k=(∑ai)2−∑ai22k=(\sum a_i)^2-\sum a_i^22k=(ai)2ai2

根据题意,1+∑(ai+1)≤1051+\sum (a_i+1)\leq 10^51+(ai+1)105,于是我们可以枚举∑ai\sum a_iai

令所有的ai=1a_i=1ai=1,那么最多能有n×n−nn\times n-nn×nn条直径。5000×5000−5000>50000005000\times 5000-5000>50000005000×50005000>5000000,这些对于题目来说是绰绰有余的了。

枚举找到第一个v=∑aiv=\sum a_iv=ai,使得v∗v−v≥2kv*v-v\geq 2kvvv2k

对于多出的部分,我们可以将若干个aia_iai组合起来,达到减少更多的效果。

比如,将两个值为1的aia_iai合并为一个值为2的aia_iai,原来减少贡献为12+12=21^2+1^2=212+12=2,现在贡献为22=42^2=422=4,增加了222

当然,如果合并三个或更多,则减少的也会更多。找到一种方法,使其减少到正好为2k2k2k即可。

code

#include<bits/stdc++.h>
using namespace std;
int n,v,now,hv,tot=0,w,vt,a[5005];
struct node{int x,y,z;
}ans[5005];
int main()
{scanf("%d",&n);for(int i=1;i<=5000;i++){if(i*i-i>=n*2){v=i;break;}}now=v*v-v-n*2;hv=v;for(int i=v;i>=2;i--){while(now>=i*i-i&&hv>=i){now-=i*i-i;hv-=i;a[++w]=i;}}for(int i=1;i<=w+hv;i++){ans[++vt]=(node){1,i+1,10000+(i>w)};}tot=w+hv+1;for(int i=1;i<=w;i++){for(int j=1;j<=a[i];j++){ans[++vt]=(node){i+1,++tot,1};}}printf("%d\n",tot);for(int i=1;i<=vt;i++){printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].z);}return 0;
}

相关文章:

【省选模拟测试23 T1直径】更好的做法

题目大意和普通做法 省选模拟测试23 T1直径 题解 对于上文中有三个儿子的根节点的树&#xff0c;其直径数量为abbccaabbccaabbcca。那么对于上文中有nnn个儿子的根节点的树&#xff0c;其直径数量为多少呢&#xff1f; 每个儿子所在子树中的点与其他儿子所在子树中的点都能组…...

SpringCloud基础(3)-微服务远程调用

SpringCloud基础1. 微服务的远程调用2. Eureka注册中心1. 搭建Eureka服务注册中心1. 微服务的远程调用 服务提供者&#xff1a;一次业务中被其它服务调用的一方&#xff1b; 服务消费者&#xff1a;一次业务中调用其它服务的一方&#xff1b; 2. Eureka注册中心 记录所有服务…...

10.单点登录原理及JWT实现

单点登录原理及JWT实现 一、单点登录效果 首先我们看通过一个具体的案例来加深对单点登录的理解。案例地址&#xff1a;https://gitee.com/xuxueli0323/xxl-sso?_fromgitee_search 把案例代码直接导入到IDEA中 然后分别修改下server和samples中的配置信息 在host文件中配置 …...

图表控件LightningChart.NET 系列教程(十一):LightningChart 组件——添加至 Blend WPF 项目

LightningChart.NET 是一款高性能 WPF 和 Winforms 图表,可以实时可视化多达1万亿个数据点。可有效利用CPU和内存资源&#xff0c;实时监控数据流。同时&#xff0c;LightningChart使用突破性创新技术&#xff0c;以实时优化为前提&#xff0c;大大提升了实时渲染的效率和效果&…...

libGDX:灯光效果实现一(实现一个点光源)

国内的libGDX文章很少&#xff0c;特别是libGDX实现灯光效果&#xff0c;所以就开始总结灯光效果的实现 绿色的框 是为了方便看到Body位置&#xff0c;使用Box2DDebugRenderer渲染的 工欲善其事&#xff0c;必先利其器&#xff0c;工具集合 gdx-setup.jar 1. 从libGDX官网下载…...

Java生态/Redis中如何使用Lua脚本

文章目录一、安装LUA1&#xff09;简单使用二、lua语法简介1、注释1&#xff09;单行注释2&#xff09;多行注释2、关键字3、变量1&#xff09;全局变量2&#xff09;局部变量4、数据类型1&#xff09;Lua数组2&#xff09;字符串操作5、if-else6、循环1&#xff09;for循环1&g…...

网络编程 socket 编程(一)

1. C/S 架构 C/S 架构即客户端/服务端架构&#xff0c;B/S 架构&#xff08;浏览器与服务端&#xff09;也是 C/S 架构的一种。 C/S 架构与 socket 的关系&#xff1a;学习 socket 可以完成 C/S 架构的开发。 2. osi 七层 一个完整的计算机系统由硬件、操作系统以及应用软件…...

【SpringCloud】SpringCloud教程之Nacos实战(一)

目录Nacos是什么&#xff1f;一.Nacos下载二.安装Nacos三.Nacos原理四.Nacos快速入门五.Nacos服务多级存储模式六.Nacos根据集群设置负载均衡1.根据同集群优先访问2.根据权重配置负载均衡七.Nacos的环境隔离八.Nacos和Eureka的区别前提&#xff1a;以订单服务和用户服务为例&am…...

高通Android 12/13 默认应用程序授予权限

1、一提到权限很多Android开发者都会想到 比如拨打电话 读取手机通讯录 定位 这些都是需要申请权限&#xff0c;Google Android 6.0之后&#xff08;sdk 23&#xff09; 需要app动态申请权限 或者权限组 2、我这里打个比方 比如需要在fm应用 默认打开mic权限 3、我们需要知道…...

代码随想录|day6|哈希表篇-- 242.有效的字母异位词 、349. 两个数组的交集 、202. 快乐数、1. 两数之和

总链接https://docs.qq.com/doc/DUEtFSGdreWRuR2p4?u329948d2f0044f34b7cbe72503f0b572 242.有效的字母异位词 链接&#xff1a;代码随想录 class Solution { public:bool isAnagram(string s, string t) {//两种做法&#xff0c;一种是int f[26]的数组,一种是map /*第一种&a…...

k8s学习之路 | Day20 k8s 工作负载 Deployment(下)

文章目录3. HPA 动态扩缩容3.1 HPA3.2 安装 metrics-server3.3 验证指标收集3.4 扩缩容的实现3.5 增加负载3.6 降低负载3.7 更多的度量指标4. 金丝雀部署4.1 蓝绿部署4.2 金丝雀部署4.3 金丝雀部署的实现5. Deployment 状态与排查5.1 进行中的 Deployment5.2 完成的 Deployment…...

考研复试——操作系统

文章目录操作系统1. 操作系统的特征&#xff1a;2. 进程与线程的关系以及区别3. 简述进程和程序的区别4. 进程的常见状态&#xff1f;以及各种状态之间的转换条件&#xff1f;5. 进程的调度算法有哪些&#xff1f;6. 什么是死锁&#xff1f;产生条件&#xff1f;如何避免死锁&a…...

Java ~ Collection/Executor ~ LinkedBlockingDeque【源码】

一 LinkedBlockingDeque&#xff08;链接阻塞双端队列&#xff09;类源码及机制详解 类 LinkedBlockingDeque&#xff08;链接阻塞双端队列&#xff09;类&#xff08;下文简称链接阻塞双端队列&#xff09;是BlockingDeqeue&#xff08;阻塞双端队列&#xff09;接口的唯一实现…...

【前缀和】截断数组、K倍区间、激光炸弹

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

函数编程:强大的 Stream API

函数编程&#xff1a;强大的 Stream API 每博一文案 只要有人的地方&#xff0c;世界就不会是冰冷的&#xff0c;我们可以平凡&#xff0c;但绝对不可以平庸。—————— 《平凡的世界》人活着&#xff0c;就得随时准备经受磨难。他已经看过一些书&#xff0c;知道不论是普通…...

企业架构图之业务架构图

在TOGAF的世界里面&#xff0c;所有的架构思想都可以通过下面三种类型的图形进行表示。 目录&#xff08;Catalogs&#xff09;矩阵&#xff08;Matrix&#xff09;图 &#xff08;Diagram&#xff09; 其架构图的本质就是用来进行沟通交流&#xff0c;通过架构图和业务团队进…...

监控易网络管理:网络流量分析

1、什么是网络流量分析2、网络流量分析的作用3、为什么要用网络流量分析功能&#xff0c;如何开启什么是网络流量分析简单的来说&#xff0c;网络流量分析就是捕捉网络中流动的数据包&#xff0c;并通过查看包内部数据以及进行相关的协议、流量、分析、统计等&#xff0c;协助发…...

RHCSA-文件内容显示(3.6)

查看命令 cat&#xff1a;显示文件内容 cat -n&#xff1a;显示文件内容的同时显示编号 tac&#xff1a;倒叙查看 head 文件名 &#xff08;默认显示前10行&#xff09;&#xff1a;显示前10行 tail&#xff1a;显示末尾行数信息 more&#xff1a;查看文件信息&#xff0c;从头…...

Qt多线程文件查找器

⭐️我叫恒心,一名喜欢书写博客的研究生在读生。 原创不易~转载麻烦注明出处,并告知作者,谢谢!!! 这是一篇近期会不断更新的博客欧~~~ 有什么问题的小伙伴 欢迎留言提问欧。 Qt多线程文件查找器 前言 最近在实现一些代码功能的时候,需要找一些多线程样例来学习,于是就…...

源码阅读笔记 InputFormat、FileInputFormat、CombineTextInputFormat

1. InputFormat InputFormat是MapReduce框架提供的用来处理job输入的基类 它主要定义了三个功能&#xff1a; 1.验证job输入是否合法 2.对输入文件进行逻辑切片(InputSplit)&#xff0c;然后将每个切片分发给单独的MapTask 3.提供切片读取器(Re…...

别再为发票报销发愁!用Python+EasyOFD库,5分钟搞定OFD转PDF/图片(附完整代码)

5分钟极速解决发票报销难题&#xff1a;PythonEasyOFD高效转换实战指南 每次月底报销时&#xff0c;面对邮箱里堆积如山的OFD格式电子发票&#xff0c;你是否也感到头疼&#xff1f;手动一张张下载、转换、打印不仅耗时耗力&#xff0c;还容易出错。今天我们就来彻底解决这个困…...

AWPortrait-Z WebUI日志诊断指南:从webui_startup.log定位90%常见问题

AWPortrait-Z WebUI日志诊断指南&#xff1a;从webui_startup.log定位90%常见问题 1. 引言&#xff1a;为什么需要关注启动日志 当你启动AWPortrait-Z WebUI时&#xff0c;系统会自动生成一个名为webui_startup.log的日志文件。这个文件就像是系统的"健康检查报告"…...

Pixel Couplet Gen效果展示:乙巳马年像素春联生成惊艳作品集

Pixel Couplet Gen效果展示&#xff1a;乙巳马年像素春联生成惊艳作品集 1. 项目概览 这是一款基于ModelScope大模型驱动的春联生成器。我们创新性地采用夸张的像素游戏风格(Retro Game UI)&#xff0c;将传统元素与红白机美学融合&#xff0c;为用户生成独一无二的马年像素春…...

乙巳马年春联生成终端参数详解:长文本生成稳定性保障机制

乙巳马年春联生成终端参数详解&#xff1a;长文本生成稳定性保障机制 1. 引言&#xff1a;当传统春联遇见现代AI 每到新年&#xff0c;家家户户贴春联是传承千年的习俗。一副好春联&#xff0c;不仅要对仗工整、平仄协调&#xff0c;更要蕴含美好的寓意。但创作一副原创的、有…...

破解Agent“半途摆烂”困局,OpenDev凭Harness架构,撕开Code Agents的工程化真相

玩过AI Agent的人&#xff0c;几乎都有过这样的崩溃时刻&#xff1a;前几轮交互里&#xff0c;它思路清晰、反应迅速&#xff0c;像个无所不能的天才&#xff0c;你说修改一段代码&#xff0c;它能精准命中漏洞&#xff1b;你让它梳理项目结构&#xff0c;它能条理分明地给出方…...

FPGA驱动OLED屏的SPI时序详解:从状态机设计到显存刷新的优化技巧

FPGA驱动OLED屏的SPI时序优化实战&#xff1a;从状态机重构到显存管理进阶 当你在调试FPGA驱动的OLED屏幕时&#xff0c;是否遇到过这些场景&#xff1a;屏幕刷新时出现肉眼可见的闪烁&#xff0c;快速切换显示内容时出现撕裂现象&#xff0c;或者当系统负载增加时显示更新变得…...

B端企业拓客:如何在精准度与成本之间找到真正平衡?氪迹科技法人股东号码核验系统,阶梯式价格

在B端市场存量竞争愈发激烈的当下&#xff0c;“拓客精准度”与“获客成本”的平衡&#xff0c;成为所有B端企业都要面对的核心课题。对绝大多数深耕B端业务的企业而言&#xff0c;拓客之路始终被两大难题困扰&#xff1a;一方面&#xff0c;线索质量参差不齐&#xff0c;空号、…...

别再只调包了!用Sentence-Transformers从零训练你的专属Embedding模型(附完整代码)

从零构建领域专属Embedding模型&#xff1a;超越调包侠的实战指南 当你第一次调用model.encode("你的文本")就能获得一个语义向量时&#xff0c;是否好奇过这个黑箱背后的魔法&#xff1f;在电商推荐、智能客服等垂直场景中&#xff0c;通用Embedding模型的表现往往差…...

Java函数计算部署实战:从本地调试到生产环境上线的7个关键步骤(含阿里云/华为云/AWS对比)

第一章&#xff1a;Java函数计算部署全景概览Java函数计算是云原生场景下轻量级、事件驱动型服务的重要实现方式。它将传统Java应用的部署范式从虚拟机/容器迁移至按需执行、自动扩缩的无服务器架构&#xff0c;显著降低运维复杂度与资源闲置成本。开发者只需聚焦业务逻辑&…...

你不知道的微信小程序环境判断技巧:wx.getAccountInfoSync()与__wxConfig深度对比

微信小程序环境判断进阶指南&#xff1a;从API到底层变量的深度解析 在微信小程序开发中&#xff0c;环境判断是一个看似简单却暗藏玄机的基础功能。许多开发者可能满足于简单的if-else判断&#xff0c;却忽略了不同判断方式对性能、稳定性和可维护性的深远影响。本文将带你深入…...