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

算法竞赛进阶指南.沙漠之王

news 来源：原创 2025/7/2 20:37:18

题目

348. 沙漠之王

算法标签: $01$ 分数规划, 最小生成树

思路

看题目有要求是构建的渠道的总长度和总成本的比值最小, 形式化的表示
$\frac {\sum L}{\sum S}$

可以转化为

$\cdot \sum S - \sum L = 0$

因为 $k$ 是变化的, 因此可以看做一个函数

$\sum L - x \cdot \sum S$

目标求解使得 $f (x) = 0$ 的最小的 $x$ , 因为 $f (x)$ 具有单调性, 因此可以二分 $x$ 求出答案

代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>using namespace std;const int N = 1010;
const double EPS = 1e-6;struct Village {int x, y, z;
} pos[N];struct Edge {int u, v;double dis, w;
} edges[N * N / 2];int n, idx;
int p[N];double calc(const Village& a, const Village& b) {int dx = a.x - b.x;int dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}bool check(double mid) {for (int i = 0; i < n; ++i) p[i] = i;vector<pair<double, pair<int, int>>> vec;for (int i = 0; i < idx; ++i) {double val = edges[i].w - mid * edges[i].dis;vec.emplace_back(val, make_pair(edges[i].u, edges[i].v));}sort(vec.begin(), vec.end());double res = 0;for (const auto& edge : vec) {int u = edge.second.first;int v = edge.second.second;int fa1 = find(u);int fa2 = find(v);if (fa1 != fa2) {p[fa2] = fa1;res += edge.first;}}return res <= 0;
}void solve() {idx = 0;for (int i = 0; i < n; ++i) {cin >> pos[i].x >> pos[i].y >> pos[i].z;}for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {double dist = calc(pos[i], pos[j]);double cost = abs(pos[i].z - pos[j].z);edges[idx++] = {i, j, dist, cost};}}double l = 0, r = 1e6;while (r - l > EPS) {double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}cout << fixed << setprecision(3) << l << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);while (cin >> n, n) solve();return 0;
}

算法竞赛进阶指南.沙漠之王

目录题目算法标签: 01 01 01分数规划, 最小生成树思路代码题目 348. 沙漠之王算法标签: 01 01 01分数规划, 最小生成树思路看题目有要求是构建的渠道的总长度和总成本的比值最小, 形式化的表示 k ∑ L ∑ S k \frac {\sum L}{\sum S} k∑S∑L 可以转化为 k ⋅…...

编程日记 2025/7/2 20:37:18

第四章：走向共产主义社会

第四章：走向共产主义社会 1. 全球无阶级社会的形成随着生产力的高度发展和社会资源的极大丰富，资本主义的最后残余彻底消失。全球范围内实现了按需分配的社会制度，所有国家都废除了货币体系和私有财产制度，进入了真正的共产主义…...

编程日记 2025/7/2 14:54:55

K8S - HPA + 探针实战 - 实现弹性扩缩与自愈

引言在分布式系统中，弹性扩缩容与服务自愈是保障业务高可用的核心能力。Kubernetes 通过自动化机制实现两大关键功能： • 动态扩缩容：基于 CPU/内存负载自动调整 Pod 副本数量，应对流量波动。 • 故障自愈：通过健…...

编程日记 2025/7/2 16:22:19

永磁同步电机控制算法--线性ADRC转速环控制器（一阶、二阶）

一、原理介绍搭建一阶、二阶线性ADRC转速环控制器，通常一阶ADRC包括一阶LTD、二阶LESO、LSEF，二阶ADRC包括二阶LTD、三阶LESO、LSEF。原理部分参考了这篇知乎自抗扰控制-ADRC - 知乎。二、仿真验证在MATLAB/simulink里面验证所提算法&#xff0c…...

编程日记 2025/7/2 15:46:10

泰迪杯特等奖案例学习资料：基于多模态数据融合与边缘计算的工业设备健康监测与预测性维护系统

（第十三届泰迪杯数据挖掘挑战赛特等奖案例解析）一、案例背景与核心挑战 1.1 应用场景与行业痛点在智能制造领域，工业设备（如数控机床、风力发电机）的健康状态直接影响生产效率和运维成本。传统维护方式存在以下问题：故障响应滞后：依赖定期检修，突发故障导致停机损…...

编程日记 2025/7/3 8:46:24

4.29[Q]NLP-Exp2

我正在完成自然语言处理作业，？阅读文档，详细解释，越细节越好 class TextCNN(object): def __init__(self, config): self.config config self.preprocessor Preprocessor(config) self.class_name {0: 负面, 1: 正面} def buil…...

编程日记 2025/7/2 20:37:13

前端开发 Markdown 编辑器与富文本编辑器详解

一、现有开源项目分析 1. Markdown 编辑器项目名称技术栈核心特性适用场景 Editor.md JavaScript/Node.js 支持 GFM、代码块、流程图、数学公式，兼容 IE8，提供主题切换功能技术博客、网页站、在线文档 Bytemd Svelte/Vue/Re…...

编程日记 2025/7/2 20:37:10

GCC-C语言“自定义段”

一、起因事情的起因是这样的，在看别人代码时，发现了一种很有意思的写法，因为本人主要是以应用层开发为主，所以对这种写法还是比较少见的，所以研究了一下，就牵扯出了一些知识点，这里先卖个关子，继续往下看。二、经过发现了一串这样的代码 static void do_mac(mcmd_…...

编程日记 2025/7/2 20:37:08

2025年4月个人工作生活总结

本文为 2025年4月工作生活总结。研发编码一个项目的临时记录自2月份领导让我牵头负责一个项目起，在本月算是有较多时间投入——但也是与之前的相比。月初，清明节前一晚上，因某事务被叫上参加临时紧急远程会议，几方领导都在…...

编程日记 2025/7/2 20:37:06

B/S架构：定义、原理及其在软件测试中的应用

引言在当今互联网时代，B/S架构已成为软件开发的主流模式之一。作为软件测试工程师，深入理解B/S架构的定义和工作原理，对于设计有效的测试策略至关重要。本文将全面解析B/S架构，并探讨其在软件测试中的特殊考量。一、B/S架构的…...

编程日记 2025/7/3 8:12:33

【Android】文件导出到本地或者U盘

项目需求在使用Android 9平板开发的时候，项目更新了一个新的需求，现在需要检测设备是否插入U盘，如果没有U盘的话，就将文件导出到系统根目录，如果有U盘的话，就将文件导出到U盘里面。项目实现 1.实现文件…...

编程日记 2025/7/2 20:37:02

在Electron中爬取CSDN首页的文章信息

背景之前分享了Electron入门的相关文章：https://gitee.com/ruirui-study/electron-demo 后来，我就想在里面多做一些演示给大家看，集成了以下功能及演示： 窗口管理、各种方法封装托盘管理菜单管理获取屏幕演示多窗口及通信演示…...

编程日记 2025/7/2 20:37:01

论文阅读：2024 EMNLP User Inference Attacks on Large Language Models

总目录大模型安全相关研究：https://blog.csdn.net/WhiffeYF/article/details/142132328 User Inference Attacks on Large Language Models https://arxiv.org/pdf/2310.09266 https://www.doubao.com/chat/4034601691207170 速览这篇论文主要研究了大语言模…...

编程日记 2025/7/2 23:02:32

学习记录：DAY21

我的开发日志：类路径扫描、DI 容器与动态代理前言我失忆了，完全不记得自己早上干了什么。日程早上 10 点左右开始，学了一早上，主要是类路径扫描相关的调试。晚上 8 点了，真不能再摸🐟了。学习记录计…...

编程日记 2025/7/2 23:02:30

服务器频繁重启日志分析与诊断

从你提供的日志来看，系统确实经历了多次重启。这个日志行显示的是： reboot system boot 6.8.0-58-generic Tue Apr 29 17:54 - 14:26 (20:31)这表示系统在4月29日17:54启动，运行了约20小时31分钟后，于次日14:26结束（可…...

编程日记 2025/7/2 23:02:28

阿里云服务迁移实战: 07-其他服务迁移

概述当完成了服务器、数据库、IP、OSS等迁移后，剩下的就是其他服务了。短信网关短信模板只能一个个创建，不能批量操作。但是可以使用以下方式优化操作。在原账号导出模板列表概述当完成了服务器、数据库、IP、OSS等迁移后，剩下的…...

编程日记 2025/7/2 23:02:26

第六章 QT基础：9、Qt中数据库的操作

Qt数据库模块概述与使用详解软件安装教程：https://subingwen.cn/qt/sql-driver/ 1. 概述 Qt框架中对数据库操作提供了很好的支持，我们可以通过Qt提供的类非常方便地和本地或者远程数据库进行连接。众所周知，数据库是 C-S（cl…...

编程日记 2025/7/2 23:02:24

DINOv2 - 无监督学习鲁棒视觉特征

本文翻译整理自：https://github.com/facebookresearch/dinov2 文章目录一、关于 DINOv2相关链接资源关键功能特性二、预训练模型预训练骨架网络通过 PyTorch Hub 加载预训练模型预训练分类头 - ImageNet预训练头 - 深度估计预训练头 - 语义分割三、安装1、推荐安…...

编程日记 2025/7/2 23:02:23

AI与无人零售：如何通过智能化技术提升消费者体验和运营效率？

引言：无人零售不只是无人值守你走进一家无人便利店，没有迎宾、没有收银员，甚至没有一个人在场，但你刚拿起商品，货架旁的摄像头就悄悄“看懂”了你的动作，系统已经在后台为你记账。你以为只是没人管&#x…...

编程日记 2025/7/2 23:02:21

STM32F10X OLED屏幕点亮

本节实现点亮OLED屏首先去原理图中查找对应引脚配置上述的IO口查看对应的原理图 OLED_CS 和 OLED_RES（PB6，PB7）就是配置为推挽输出OLED_SCLK 和 OLED_SDIN （PB13 PB15）OLED_D/C (PE12) 推挽输出就…...

编程日记 2025/7/2 23:02:19

Nginx核心功能02

目录一：正向代理 1.编译安装nginx 2.配置正向代理二：反向代理 1.配置nginx七层代理 2.配置nginx四层代理（传输层，TCP/UDP） 三：nginx缓存 1.缓存功能的核心原理和缓存类型 2.代理缓存功能设置四…...

编程日记 2025/7/2 11:31:25

微格式：为Web内容赋予语义的力量

一、什么是微格式？微格式是一种建立在已有 Web 标准基础上的简单、开放的数据格式。它的核心思想是通过在 HTML 标签中添加特定的属性和类名，为网页内容添加语义注解，从而兼顾 HTML 文档的人机可读性。简单来说，微格式就是一套约定俗成的 HTML 标记方式，让我们能够在不…...

编程日记 2025/7/3 9:11:27

Linux基础 -- Generic Netlink 框架详解与开发实践

Generic Netlink 框架详解与开发实践本文旨在系统性介绍 Linux 内核中的 Generic Netlink 框架，包括其设计背景、结构设计、核心数据结构 genl_ops 的使用，以及完整的内核与用户态通信示例，适合用于驱动开发、用户空间控制接口构建及系统通信…...

编程日记 2025/7/2 23:02:14

CMake解析参数用法示例

cmake_parse_arguments 是 CMake 中用于解析函数或宏参数的工具，特别适合处理带有选项（OPTIONS）、单值参数（SINGLE_ARGS）和多值参数（MULTI_ARGS）的复杂参数列表。以下是用法说明和一个示例&…...

编程日记 2025/7/2 23:02:13

开源项目实战学习之YOLO11：ultralytics-cfg-models-fastsam（九）

👉 点击关注不迷路 👉 点击关注不迷路 👉 点击关注不迷路文章大纲 1. __init__.py2. model.py3. predict.py4. utils.py5. val.py FastSAM 是一种目标检测和图像分割模型，Ultralytics 是一个在计算机视觉领域广泛使用的库&#x…...

编程日记 2025/7/2 23:02:11

使用frpc链接内网的mysql

以下是配置 frpc 连接内网 MySQL 服务的详细步骤： 1. 准备工作 frps 服务器：已部署在公网 IP 11.117.11.245，假设 frps 的默认端口为 7000。内网 MySQL 服务：运行在内网机器的 3306 端口。目标：通过公网 IP 11.117…...

编程日记 2025/7/2 1:20:36

分享:VTK版本的选择 - WPF空域问题

在早期版本中，ActiViz 对 Windows Presentation Foundation (WPF) 框架的支持是通过 WindowsFormHost 组件实现的，这种方式依赖于 WindowsForm 和 WPF 的互操作性。然而，这种方法存在一个众所周知的“空域问题”（airspace issue&a…...

编程日记 2025/7/2 21:40:55

MIPS架构详解：定义、应用与其他架构对比

一、MIPS架构的定义 MIPS（Microprocessor without Interlocked Pipeline Stages） 是一种经典的精简指令集（RISC）处理器架构，由斯坦福大学John Hennessy团队于1981年提出，强调高效流水线设计和硬件简化。核…...

编程日记 2025/7/2 23:02:05

项目剖析:基于Agent的个人知识管理系统如何设计

为什么写这篇文章？最近在思考如果想要构建一个个人知识管理的Agent应该怎样设计才好，然后最近看到这样一个项目，就想剖析一下它的架构，看一下它的设计思想。然后一些剖析得过程就沉淀到本文当中。本文档主要从整体架构、dataflow的视角剖析khoj项目，分析应该一个知识管理A…...

编程日记 2025/7/2 23:02:04

Python魔法函数深度解析

一、魔法函数是什么？ 魔法函数（Magic Methods）是Python中以双下划线（__xx__）包裹的特殊方法，它们为类提供了一种与Python内置语法深度集成的能力。这些方法由解释器自动调用，无需显式调用&…...

编程日记 2025/7/2 23:02:02

PCB设计工艺规范（一）概述

PCB设计工艺规范（一） 1.概述2.关键词及引用标准3.PCB板材要求3.1 确定PCB使用板材以及TG值3.2 确定 PCB 的表面处理镀层 4.热设计要求5.器件库选项要求资料来自网络，仅供学习使用。 1.概述规范产品的 PCB 工艺设计，规定 PCB 工…...

编程日记 2025/7/2 23:02:00

Github开通第三方平台OAuth登录及Java对接步骤

调研起因： 准备搞AI Agent海外项目，有相当一部分用户群体是程序员，所以当然要接入Github这个全球最大的同性交友网站了，让用户使用Github账号一键完成注册或登录。本教程基于Web H5界面进行对接，同时也提供了spring-…...

编程日记 2025/7/2 23:01:58

DeepSeek V1：初代模型的架构与性能

DeepSeek V1（又称DeepSeek-MoE）是DeepSeek系列的首代大规模语言模型，它采用Transformer结合稀疏混合专家（MoE）的创新架构，实现了在受控算力下的大容量模型。本文将深入解析DeepSeek V1的架构设计与技术细节，包括其关键机制、训练优化策略，以及在各类NLP任务上的表现。 …...

编程日记 2025/7/2 23:01:56

Java ResourceBundle 资源绑定详解

Java ResourceBundle 资源绑定详解 ResourceBundle 是 Java 提供的国际化（i18n）资源管理工具，位于 java.util 包。它专门用于加载本地化的 .properties 资源文件，支持多语言切换，是国际化和本地化开发的核心类。 1. 核心特性（1）基本特点基于 .properties 文件管理键…...

编程日记 2025/7/2 23:01:55

flutter 专题六十一支持上拉加载更多的自定义横向滑动表格

在股票软件中，经常会看到如下所示的效果（ps：由于公司数据敏感，所以使用另一个朋友的一个图）。分析需要后，我先在网上找了下支持横向滑动的组件，最后找到了这个：flutter_horizontal…...

编程日记 2025/7/2 23:01:53

暗夜模式续

之前写过一篇笨拙的方式实现暗夜模式，但是当真正去适配的时候发现简直恶心至极；然后想通过一些方式可以把笨拙的方式变得优雅； 之前实现暗夜模式的快速通道，这篇文章在基于这个基础上优化而来目录背景优化步骤 OK&#xf…...

编程日记 2025/7/2 7:42:45

[吾爱出品] 文件夹迁移工具（DirMapper）

文件夹迁移工具（DirMapper） 链接：https://pan.xunlei.com/s/VOP4Uf6vu3dalYLaZ1iZUhJ1A1?pwdfhzi# 文件夹迁移工具（DirMapper） 智能识别源文件夹分类复制/移动两种迁移模式冲突解决方案（覆盖/跳过/合…...

编程日记 2025/7/2 23:01:48

DeepSeek 4月30日发布新模型：DeepSeek-Prover-V2-671B 可进一步降低数学AI应用门槛，推动教育、科研领域的智能化升级

DeepSeek-Prover-V2-671B模型特点： 一、超大参数规模与数学推理能力参数规模跃升模型参数量高达6710亿，是前代数学推理模型Prover-V1.5（70亿参数）的近100倍，表明其具备更强的复杂问题处理能力。前代Prover-V1.5在高…...

编程日记 2025/7/2 23:01:46

GitHub修炼法则：第一次提交代码教学(Liunx系统)

前言 github是广大程序员们必须要掌握的一个技能，万事开头难，如果成功提交了第一次代码，那么后来就会简单很多。网上的相关资料往往都不是从第一次开始，导致很多新手们会在过程中遇到很多权限认证相关的问题，进而被卡…...

编程日记 2025/7/2 23:01:45

百家号等新媒体私信入口是否可以聚合到企业微信的客服，如何实现

一、技术实现路径 1. 百家号 API 对接接口权限申请： 登录百度开发者平台，创建应用并获取 API 密钥（app_id和app_token）。申请私信相关接口权限（如消息通知、粉丝查询），需满足百家号的审核要求…...

编程日记 2025/7/2 23:01:43

【来自AI】RS485，Rs232，Modbus的区别和联系是什么

RS485、RS232 和 Modbus 是常用于工业自动化和通信中的技术标准，它们有不同的特点和应用。下面是它们的区别和联系： RS232 (Recommended Standard 232) 定义：RS232 是一种串行通信标准，通常用于短距离（一般最多15米&…...

编程日记 2025/7/2 23:01:41

java实现序列化与反序列化

va 实现序列化与反序列化序列化（Serialization） 是将 Java 对象转换为字节流（二进制数据），以便存储或网络传输。反序列化（Deserialization） 则是将字节流恢复为 Java 对象。 Java 提供了 ja…...

编程日记 2025/7/2 21:37:43

harmonyOS 手机，双折叠，平板，PC端屏幕适配

由于HarmonyOS设备的屏幕尺寸和分辨率各不相同，开发者需要采取适当的措施来适配不同的屏幕。 1.EntryAbility.ets文件里：onWindowStageCreate方法里判断设备类型， 如果是pad，需全屏展示（按客户需求来，本次…...

编程日记 2025/7/2 23:01:39

Qt Creator环境编译的Release软件放在其他电脑上使用方法

本文解决的问题：将Qt Creator环境编译的exe可执行程序放到其他电脑上不可用情况 1、寻找windeployqt工具所在路径" D:\Qt5.12.10\5.12.10\msvc2015_64\bin" ，将此路径配置到环境变量； 2、用Qt Creator环境编译出Release版本可执行…...

编程日记 2025/7/2 23:01:38

electron+vite+vue3 快速入门教程

Electron、Vite 和 Vue 3 结合使用可以创建强大的跨平台桌面应用程序，下面是一个快速入门教程，帮助你搭建一个基于 Electron Vite Vue 3 的项目。环境准备 Node.js: 首先确保你的机器上已经安装了 Node.js。你可以通过以下命令来检查是否已安装&…...

编程日记 2025/7/2 20:36:59

添加了addResourceHandlers 但没用

B站黑马的视频 public class WebMvcConfig extends WebMvcConfigurationSupport { /** * 设置静态资源映射 * param registry */ Override protected void addResourceHandlers(ResourceHandlerRegistry registry) { log.info("开始进…...

编程日记 2025/7/2 23:01:36