[树] 最轻的天平
问题描述
天平的两边有时不一定只能挂物品,还可以继续挂着另一个天平,现在给你一些天平的情况和他们之间的连接关系,要求使得所有天平都能平衡所需物品的总重量最轻。
一个天平平衡当且仅当“左端点的重量 × \times × 左端点到支点的距离 = = = 右端点的重量 × \times × 右端点到支点的距离。
输入格式
第一行包含一个 N ( N ≤ 100 ) N(N \le 100) N(N≤100),表示天平的数量,天平编号为 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×L≤231,其中 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} N≤100,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;
}
相关文章:

[树] 最轻的天平
问题描述 天平的两边有时不一定只能挂物品,还可以继续挂着另一个天平,现在给你一些天平的情况和他们之间的连接关系,要求使得所有天平都能平衡所需物品的总重量最轻。 一个天平平衡当且仅当“左端点的重量 \times 左端点到支点的距离 …...
Linux udev介绍使用
udev udev配置文件匹配键和赋值键操作符解释示例修改udev配置U盘自动挂载Usb卸载SD卡挂载SD卡卸载 udev配置文件 /etc/udev/udev.conf 这个文件通常很短,他可能只是包含几行#开头的注释,然后有几行选项: udev_root“/dev/” udev_rules“/…...
单片机:实现节日彩灯(附带源码)
本项目的目标是通过编程实现几个常见的彩灯效果,包括: 流水灯效果(从左到右或从右到左)闪烁效果(所有灯同时闪烁)渐变效果(灯光从亮到灭,再从灭到亮)定时切换颜色效果&a…...

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

【爬虫一】python爬虫基础合集一
【爬虫一】python爬虫基础合集一 1. 网络请求了解1.1. 请求的类型1.2. 网络请求协议1.3. 网络请求过程简单图解1.4. 网络请求Headers(其中的关键字释义):请求头、响应头 2. 网络爬虫的基本工作节点2.1. 了解简单网络请求获取响应数据的过程所涉及要点 1. 网络请求了…...
any/all 子查询优化规则的原理与解析 | OceanBase查询优化
背景 在通常情况下,当遇到包含any/all子查询的语句时,往往需要遵循嵌套执行的方式,因此其查询效率较低。Oceanbase中制定了相应的any/all子查询优化规则,能够能够识别并优化符合条件的any/all子查询,从而有效提升查询…...
ECharts 饼图:数据可视化的重要工具
ECharts 饼图:数据可视化的重要工具 引言 在数据分析和可视化的领域,ECharts 是一个广受欢迎的开源库。它由百度团队开发,用于在网页中创建交互式图表。ECharts 提供了多种图表类型,包括柱状图、折线图、散点图等,而饼图则是其中最常用的一种。本文将深入探讨 ECharts 饼…...
第10章:CSS最佳实践 --[CSS零基础入门]
代码组织 在CSS开发中,良好的代码组织和最佳实践对于项目的可维护性和扩展性至关重要。以下是两个示例,展示了如何遵循CSS最佳实践来组织代码。 示例 1: 使用 BEM(Block Element Modifier)命名法 BEM 是一种用于提高 CSS 可读性…...

怎么在idea中创建springboot项目
最近想系统学习下springboot,尝试一下全栈路线 从零开始,下面将叙述下如何创建项目 环境 首先确保自己环境没问题 jdkMavenidea 创建springboot项目 1.打开idea,选择file->New->Project 2.选择Spring Initializr->设置JDK->…...
递归读取指定目录下的文件
序言 需要读取sftp服务器上符合指定的文件名正则的文件列表,目前想到的最好的办法就是递归。 我这里引入的依赖是: <!-- jsch-sftp连接 --><dependency><groupId>com.jcraft</groupId><artifactId>jsch</artif…...

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

常用的JVM启动参数有哪些?
大家好,我是锋哥。今天分享关于【常用的JVM启动参数有哪些?】面试题。希望对大家有帮助; 常用的JVM启动参数有哪些? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 JVM(Java Virtual Machine)启…...
Curvelet 变换与FDCT
Curvelet变换 Curvelet变换 是一种多尺度、多方向的信号分析工具,专门用于处理具有各向异性特征的信号,例如边缘和曲线。与传统的傅里叶变换和小波变换相比,Curvelet变换能够更精确地表示信号中的曲线特征,因此在图像处理、地震数据分析、医学成像等领域得到了广泛应用。 …...

Django Admin 管理工具
Django 提供了基于 web 的管理工具。 Django 自动管理工具是 django.contrib 的一部分。你可以在项目的 settings.py 中的 INSTALLED_APPS 看到它: /HelloWorld/HelloWorld/settings.py 文件代码: 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)中的应用:以资产回报矩阵为例(中英双语)
本文中的例子来源于: 这本书,网址为:https://web.stanford.edu/~boyd/vmls/ 矩阵在资产收益(Asset Returns)中的应用:以资产回报矩阵为例 在量化金融中,矩阵作为一种重要的数学工具,被广泛用于描述和分析…...

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

【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#经典算法面试题,分享给大家 # 递归算法 ## C#递归算法计算阶乘的方法 > 一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。1808年,基斯顿…...

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

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

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

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...

Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...

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

CSS3相关知识点
CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...