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

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...

webpack面试题

面试题&#xff1a;webpack介绍和简单使用 一、webpack&#xff08;模块化打包工具&#xff09;1. webpack是把项目当作一个整体&#xff0c;通过给定的一个主文件&#xff0c;webpack将从这个主文件开始找到你项目当中的所有依赖文件&#xff0c;使用loaders来处理它们&#x…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...