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

[树] 最轻的天平

问题描述

天平的两边有时不一定只能挂物品,还可以继续挂着另一个天平,现在给你一些天平的情况和他们之间的连接关系,要求使得所有天平都能平衡所需物品的总重量最轻。

一个天平平衡当且仅当“左端点的重量 × \times × 左端点到支点的距离 = = = 右端点的重量 × \times × 右端点到支点的距离。

在这里插入图片描述

输入格式

第一行包含一个 N ( N ≤ 100 ) N(N \le 100) N(N100),表示天平的数量,天平编号为 1 1 1 N N N

接下来包含 N N N 行描述天平的情况,每行 4 4 4 个整数 P , Q , R , B P,Q,R,B P,Q,R,B P P P Q Q Q 表示横杆上支点到左边的长度与到右边的距离的比例为 P : Q P:Q P:Q R R R 表示左边悬挂的情况,如果 R = 0 R = 0 R=0 说明悬挂的物品,否则表示左边悬挂的是天平 R R R B B B 表示右边的悬挂情况,如果 B = 0 B = 0 B=0 表示右边悬挂的是物品,否则右边悬挂着天平 B B B

对于所有的输入,保证 W × L ≤ 2 31 W \times L \le 2^{31} W×L231,其中 W W W 为最轻的物品重量,而 L L L 为输入中描述左右比例时出现的最大值。

输出格式

输出一个整数表示使得所有天平都平衡所需最轻的物品总重量。

样例

样例输入1:

4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0

样例输出1:

40

数据范围

对于所有数据, N ≤ 100 , W × L < 2 31 N \le 100,W \times L < 2^{31} N100,W×L<231

题解

考虑第 i i i 个天平,假设左右最轻重量为 W 1 , W 2 W1, W2 W1,W2,比例为 L 1 : L 2 L1:L2 L1:L2,当前需要左右放 X X X Y Y Y
X X X Y Y Y 需要满足: W 1 × L 1 × X = W 2 × L 2 × Y W1 \times L1 \times X = W2 \times L2 \times Y W1×L1×X=W2×L2×Y
移项可得: X Y = W 2 × L 2 W 1 × L 1 \frac{X}{Y} = \frac{W2 \times L2}{W1 \times L1} YX=W1×L1W2×L2
因此,天平重量最小,必须将 x y \frac{x}{y} yx 化为最简分数。
求出 W 2 × L 2 W2 \times L2 W2×L2 W 1 × L 1 W1 \times L1 W1×L1 的最大公因数 P P P X = W 2 × L 2 × P X = W2 \times L2 \times P X=W2×L2×P Y = W 1 × L 1 × P Y = W1 \times L1 \times P Y=W1×L1×P
重量为 X × W 1 + Y × W 2 X \times W1 + Y \times W2 X×W1+Y×W2
处理时直接递归求解

#define int long long
int dfs(int x){if(x == 0){//边界return 1;}int t1 = dfs(l[x]), t2 = dfs(r[x]);int t = __gcd(a[x] * t1, b[x] * t2);return t1 * a[x] * t2 / t + t2 * b[x] * t1 / t;
}
signed main(){scanf("%d", &n);for(int i = 1; i <= n; ++ i){scanf("%d %d %d %d", &a[i], &b[i], &l[i], &r[i]);f[l[i]] = 1;f[r[i]] = 1;}int rt = 0;for(int i = 1; i <= n; ++ i){if(!f[i]){rt = i;break;}}printf("%lld", dfs(rt));return 0;
}

相关文章:

[树] 最轻的天平

问题描述 天平的两边有时不一定只能挂物品&#xff0c;还可以继续挂着另一个天平&#xff0c;现在给你一些天平的情况和他们之间的连接关系&#xff0c;要求使得所有天平都能平衡所需物品的总重量最轻。 一个天平平衡当且仅当“左端点的重量 \times 左端点到支点的距离 …...

Linux udev介绍使用

udev udev配置文件匹配键和赋值键操作符解释示例修改udev配置U盘自动挂载Usb卸载SD卡挂载SD卡卸载 udev配置文件 /etc/udev/udev.conf 这个文件通常很短&#xff0c;他可能只是包含几行#开头的注释&#xff0c;然后有几行选项&#xff1a; udev_root“/dev/” udev_rules“/…...

单片机:实现节日彩灯(附带源码)

本项目的目标是通过编程实现几个常见的彩灯效果&#xff0c;包括&#xff1a; 流水灯效果&#xff08;从左到右或从右到左&#xff09;闪烁效果&#xff08;所有灯同时闪烁&#xff09;渐变效果&#xff08;灯光从亮到灭&#xff0c;再从灭到亮&#xff09;定时切换颜色效果&a…...

流程引擎Activiti性能优化方案

流程引擎Activiti性能优化方案 Activiti工作流引擎架构概述 Activiti工作流引擎架构大致分为6层。从上到下依次为工作流引擎层、部署层、业务接口层、命令拦截层、命令层和行为层。 基于关系型数据库层面优化 MySQL建表语句优化 Activiti在MySQL中创建默认字符集为utf8&…...

【爬虫一】python爬虫基础合集一

【爬虫一】python爬虫基础合集一 1. 网络请求了解1.1. 请求的类型1.2. 网络请求协议1.3. 网络请求过程简单图解1.4. 网络请求Headers(其中的关键字释义)&#xff1a;请求头、响应头 2. 网络爬虫的基本工作节点2.1. 了解简单网络请求获取响应数据的过程所涉及要点 1. 网络请求了…...

any/all 子查询优化规则的原理与解析 | OceanBase查询优化

背景 在通常情况下&#xff0c;当遇到包含any/all子查询的语句时&#xff0c;往往需要遵循嵌套执行的方式&#xff0c;因此其查询效率较低。Oceanbase中制定了相应的any/all子查询优化规则&#xff0c;能够能够识别并优化符合条件的any/all子查询&#xff0c;从而有效提升查询…...

ECharts 饼图:数据可视化的重要工具

ECharts 饼图:数据可视化的重要工具 引言 在数据分析和可视化的领域,ECharts 是一个广受欢迎的开源库。它由百度团队开发,用于在网页中创建交互式图表。ECharts 提供了多种图表类型,包括柱状图、折线图、散点图等,而饼图则是其中最常用的一种。本文将深入探讨 ECharts 饼…...

第10章:CSS最佳实践 --[CSS零基础入门]

代码组织 在CSS开发中&#xff0c;良好的代码组织和最佳实践对于项目的可维护性和扩展性至关重要。以下是两个示例&#xff0c;展示了如何遵循CSS最佳实践来组织代码。 示例 1: 使用 BEM&#xff08;Block Element Modifier&#xff09;命名法 BEM 是一种用于提高 CSS 可读性…...

怎么在idea中创建springboot项目

最近想系统学习下springboot&#xff0c;尝试一下全栈路线 从零开始&#xff0c;下面将叙述下如何创建项目 环境 首先确保自己环境没问题 jdkMavenidea 创建springboot项目 1.打开idea&#xff0c;选择file->New->Project 2.选择Spring Initializr->设置JDK->…...

递归读取指定目录下的文件

序言 需要读取sftp服务器上符合指定的文件名正则的文件列表&#xff0c;目前想到的最好的办法就是递归。 我这里引入的依赖是&#xff1a; <!-- jsch-sftp连接 --><dependency><groupId>com.jcraft</groupId><artifactId>jsch</artif…...

【模型压缩】原理及实例

在移动智能终端品类越发多样的时代&#xff0c;为了让模型可以顺利部署在算力和存储空间都受限的移动终端&#xff0c;对模型进行压缩尤为重要。模型压缩&#xff08;model compression&#xff09;可以降低神经网络参数量&#xff0c;减少延迟时间&#xff0c;从而实现提高神经…...

常用的JVM启动参数有哪些?

大家好&#xff0c;我是锋哥。今天分享关于【常用的JVM启动参数有哪些&#xff1f;】面试题。希望对大家有帮助&#xff1b; 常用的JVM启动参数有哪些&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 JVM&#xff08;Java Virtual Machine&#xff09;启…...

Curvelet 变换与FDCT

Curvelet变换 Curvelet变换 是一种多尺度、多方向的信号分析工具,专门用于处理具有各向异性特征的信号,例如边缘和曲线。与传统的傅里叶变换和小波变换相比,Curvelet变换能够更精确地表示信号中的曲线特征,因此在图像处理、地震数据分析、医学成像等领域得到了广泛应用。 …...

Django Admin 管理工具

Django 提供了基于 web 的管理工具。 Django 自动管理工具是 django.contrib 的一部分。你可以在项目的 settings.py 中的 INSTALLED_APPS 看到它&#xff1a; /HelloWorld/HelloWorld/settings.py 文件代码&#xff1a; INSTALLED_APPS ( django.contrib.admin, django.co…...

Android笔记【19】

具体示例 run: val result someObject.run {// 这里可以使用 thisthis.someMethod() }let: val result someObject?.let {// 这里使用 itit.someMethod() }with: val result with(someObject) {// 这里使用 thissomeMethod() }apply: val obj SomeClass().apply {// 这里使…...

矩阵在资产收益(Asset Returns)中的应用:以资产回报矩阵为例(中英双语)

本文中的例子来源于&#xff1a; 这本书&#xff0c;网址为&#xff1a;https://web.stanford.edu/~boyd/vmls/ 矩阵在资产收益(Asset Returns)中的应用&#xff1a;以资产回报矩阵为例 在量化金融中&#xff0c;矩阵作为一种重要的数学工具&#xff0c;被广泛用于描述和分析…...

Docker 中如何限制CPU和内存的使用 ?

在容器化的动态世界中&#xff0c;Docker 已经成为构建、部署和管理容器化的关键工具应用。然而&#xff0c;Docker 的效率在很大程度上取决于资源管理得有多好。设置适当的内存和 CPU 限制对于优化 Docker 性能至关重要&#xff0c;确保每个容器在不使主机负担过重的情况下获得…...

【AIGC-ChatGPT进阶提示词-《动图生成》】怪物工厂:融合想象力与创造力的奇幻世界

引言 在这个科技飞速发展的时代,人工智能正在不断突破我们的想象。而在众多AI应用中,有一个独特的创意工具正在悄然兴起,它就是"怪物工厂"。这个神奇的工具能够将人类天马行空的想象力与AI的创造力完美结合,打造出一个个奇异、有趣、甚至有些恐怖的怪物形象。本…...

docker 使用 xz save 镜像

适用场景 如果docker save -o xxx > xxx 镜像体积过大,可以使用 xz 命令压缩。 命令 例如 save busybox:1.31.1 镜像,其中 -T 是使用多核心压缩,可以加快压缩。 docker save busybox:1.31.1 |xz -T 8 > /tmp/busybox:1.31.1安装 xz Ubuntu/Debian sudo apt upda…...

C#经典算法面试题

网络上收集的一些C#经典算法面试题&#xff0c;分享给大家 # 递归算法 ## C#递归算法计算阶乘的方法 > 一个正整数的阶乘&#xff08;factorial&#xff09;是所有小于及等于该数的正整数的积&#xff0c;并且0的阶乘为1。自然数n的阶乘写作n!。1808年&#xff0c;基斯顿…...

C++笔记 继承关系中构造和析构顺序(面向对象)

在C面向对象编程中&#xff0c;继承是实现代码复用和类层次设计的核心特性。当存在基类与派生类的继承关系时&#xff0c;构造函数和析构函数的调用顺序有严格的规则——这不仅是面试高频考点&#xff0c;更是避免内存泄漏、保证对象正确初始化/清理的关键。核心结论先明确&…...

Kandinsky-5.0-I2V-Lite-5s保姆级教程:从访问https://gpu-1pm4kagkou-7860.web.gpu.csdn.net/开始

Kandinsky-5.0-I2V-Lite-5s保姆级教程&#xff1a;从访问https://gpu-1pm4kagkou-7860.web.gpu.csdn.net/开始 1. 认识Kandinsky-5.0-I2V-Lite-5s Kandinsky-5.0-I2V-Lite-5s是一款轻量级的图生视频模型&#xff0c;它能将静态图片转化为动态视频。你只需要上传一张图片&…...

企业员工福利平台选型:技术架构与对接难点拆解

企业员工福利平台选型&#xff1a;技术架构与对接难点拆解“选对企业员工福利平台&#xff0c;技术架构与系统对接是决定落地成败的关键——忽略技术适配性的选型&#xff0c;往往会让福利项目陷入‘上线易、用着难’的困境。”随着企业数字化转型加速&#xff0c;员工福利从“…...

Z-Image Turbo实际作品分享:城市风光生成效果

Z-Image Turbo实际作品分享&#xff1a;城市风光生成效果 本文所有内容均为技术效果展示&#xff0c;不涉及任何政治敏感内容&#xff0c;所有案例均为技术演示用途。 1. 效果概览&#xff1a;城市风光的AI艺术呈现 Z-Image Turbo作为基于Gradio和Diffusers构建的高性能AI绘图…...

微信QQ防撤回神器:RevokeMsgPatcher 2.1 终极使用教程

微信QQ防撤回神器&#xff1a;RevokeMsgPatcher 2.1 终极使用教程 【免费下载链接】RevokeMsgPatcher :trollface: A hex editor for WeChat/QQ/TIM - PC版微信/QQ/TIM防撤回补丁&#xff08;我已经看到了&#xff0c;撤回也没用了&#xff09; 项目地址: https://gitcode.co…...

**雾计算中的边缘智能:基于Python的轻量级任务调度系统设计与实现**在物联网(IoT)飞速发展的今天,传统云

雾计算中的边缘智能&#xff1a;基于Python的轻量级任务调度系统设计与实现 在物联网&#xff08;IoT&#xff09;飞速发展的今天&#xff0c;传统云计算模式已难以满足低延迟、高带宽和实时响应的需求。**雾计算&#xff08;Fog Computing&#xff09;**作为云与终端设备之间的…...

Java边缘容器化部署卡顿难题(2024最新LTS版HotSpot深度调优白皮书)

第一章&#xff1a;Java边缘容器化部署卡顿难题&#xff08;2024最新LTS版HotSpot深度调优白皮书&#xff09;在边缘计算场景下&#xff0c;资源受限的ARM64设备&#xff08;如Jetson Orin、Raspberry Pi 5&#xff09;运行JDK 21.0.3 LTS&#xff08;2024年4月发布&#xff09…...

Unity URP 中 Mipmap 纹理多级渐远技术 解决远处纹理闪烁(摩尔纹)与性能优化的完整指南

什么是 Mipmap&#xff1f;Mipmap&#xff08;多重贴图渐远技术&#xff09;是一种经典的纹理渲染优化技术。它为每张纹理生成一系列预计算的缩小版本&#xff0c;从原始分辨率开始&#xff0c;逐级缩小至 11 像素。工作原理当 3D 场景中的物体远离摄像机时&#xff0c;其在屏幕…...

如何通过霞鹜文楷解决中文开源字体在技术项目中的核心挑战

如何通过霞鹜文楷解决中文开源字体在技术项目中的核心挑战 【免费下载链接】LxgwWenKai An unprofessional open-source Chinese font derived from Fontworks Klee One. 一款非专业的开源中文字体&#xff0c;基于 FONTWORKS 出品字体 Klee One 衍生。 项目地址: https://g…...

w3x2lni:魔兽地图跨版本兼容解决方案技术指南

w3x2lni&#xff1a;魔兽地图跨版本兼容解决方案技术指南 【免费下载链接】w3x2lni 魔兽地图格式转换工具 项目地址: https://gitcode.com/gh_mirrors/w3/w3x2lni 价值定位&#xff1a;破解魔兽地图版本壁垒 当你尝试在1.32.8版本魔兽争霸III中运行经典的1.24.4地图时&…...