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

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

深入理解 React 样式方案

React 的样式方案较多,在应用开发初期,开发者需要根据项目业务具体情况选择对应样式方案。React 样式方案主要有: 1. 内联样式 2. module css 3. css in js 4. tailwind css 这些方案中,均有各自的优势和缺点。 1. 方案优劣势 1. 内联样式: 简单直观,适合动态样式和…...

CentOS 7.9安装Nginx1.24.0时报 checking for LuaJIT 2.x ... not found

Nginx1.24编译时&#xff0c;报LuaJIT2.x错误&#xff0c; configuring additional modules adding module in /www/server/nginx/src/ngx_devel_kit ngx_devel_kit was configured adding module in /www/server/nginx/src/lua_nginx_module checking for LuaJIT 2.x ... not…...

IP选择注意事项

IP选择注意事项 MTP、FTP、EFUSE、EMEMORY选择时&#xff0c;需要考虑以下参数&#xff0c;然后确定后选择IP。 容量工作电压范围温度范围擦除、烧写速度/耗时读取所有bit的时间待机功耗擦写、烧写功耗面积所需要的mask layer...

Vue3学习(接口,泛型,自定义类型,v-for,props)

一&#xff0c;前言 继续学习 二&#xff0c;TS接口泛型自定义类型 1.接口 TypeScript 接口&#xff08;Interface&#xff09;是一种定义对象形状的强大工具&#xff0c;它可以描述对象必须包含的属性、方法和它们的类型。接口不会被编译成 JavaScript 代码&#xff0c;仅…...

分类数据集 - 场景分类数据集下载

数据集介绍&#xff1a;自然场景分类数据集&#xff0c;真实场景高质量图片数据&#xff1b;适用实际项目应用&#xff1a;自然场景下场景分类项目&#xff0c;以及作为通用场景分类数据集场景数据的补充&#xff1b;数据集类别&#xff1a;buildings、forest、glacier、mounta…...