网站建设供需/站长工具查询入口
《算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。
文章目录
- 题目描述
- 题解
- C++代码
- Java代码
- Python代码
“ 单位转换” ,链接: http://oj.ecustacm.cn/problem.php?id=2136
题目描述
【题目描述】 给定 n 组单位换算关系式,q 组询问,每次将某个单位转换成另一个单位。
单位换算关系式:1 = 。表示左边的 1 个单位的 等价于 个单位的 。
询问格式: to 。询问 个单位的 等价于多少个单位的 。
【输入格式】 输入第一行为正整数 n,q。1≤n≤100,1≤q≤10000。
接下来 n 行,每行均为:1 <unitA> = <value> <unitB>。
接下来 q 行,每行均为: <unitA> to <unitB>。
其中<value>为浮点数 v,属于区间 [0.001,1000],小数点后最多 9 位数字。
<unitA>,<unitB>最多包含 20 个小写字母。
查询中的单位保证至少在一个单位转换等式中有定义。每个单位最多只能以一种方式转换为其他任何单位。
【输出格式】 对于每个查询,输出所请求单位的值,如果无法回答查询,则输出“impossible”。
输出结果与标准答案绝对误差或者相对误差不超过 10-6 被视为正确。
【输入样例】
样例1:
4 3
1 foot = 12 inch
1 yard = 3 foot
1 meter = 100 centimeter
1 centimeter = 10 millimeter
750 millimeter to meter
42 yard to inch
10 meter to foot样例2:
4 3
1 fortnight = 14 day
1 microcentury = 0.036525 day
1 microcentury = 1000 nanocentury
1 week = 7 day
22.2 fortnight to nanocentury
2.5 nanocentury to week
3.14 day to fortnight样例3:
10 2
1 micrometer = 1000 nanometer
1 millimeter = 1000 micrometer
1 meter = 1000 millimeter
1 kilometer = 1000 meter
1 megameter = 1000 kilometer
1 lightsecond = 299.792458 meter
1 lightminute = 60 lightsecond
1 lighthour = 60 lightminute
1 lightday = 24 lighthour
1 lightyear = 365.25 lightday
42 nanometer to lightyear
42 lightyear to nanometer
【输出样例】
样例1:
0.75
1512
impossible样例2:
8509240.2464065708427
1.3044642857142857142e-05
0.22428571428571428572样例3:
4.439403502903384947e-18
3.9735067984839359997e+20
题解
把本题直接建模为图上路径问题。把单位unit看成点,把换算值value看成边,那么所有的单位换算关系式就转换成了图,图中有一些互相连通的子图。
查询时,若两个点(两个单位)在一个连通子图上,找到路径,计算路径之积(把这条路径上的所有边的转换值累乘)就是答案;如果不在一个连通子图上,输出“impossible”。
本题只需找到一条路径即可,并不一定需要找最短路径。用什么路径算法?如果是在普通图上找路径,应该用Dijkstra这样的算法。如果用DFS,可能需要搜天量的路径,导致超时。
本题的连通子图是什么形状?题目限制“每个单位最多只能以一种方式转换为其他任何单位”,也就是说两个点之间只有一条路径,这意味着这个连通子图是一棵树。在一棵树上,两点间的路径只有1条,用DFS编码最简单,一次路径计算的复杂度是O(n)的。
建图时,一个换算关系式是一条有向边,但是可以反向转换,例如“1 fortnight = 14 day”反过来是“1 day = 1/14 fortnight”。这样一条有向边实际上是双向边,或者看成无向边。
【重点】 DFS路径 。
C++代码
代码要点是:(1)用最常用的邻接表存图;(2)用map把单位转为唯一的数字;(3)用dfs搜索一条路径,并计算路径之积。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
map<string, int>id; //用map把单位转为唯一的数字
int cnt = 0;
int get_id(string s){ //查询单位对应的数字if(id.count(s)) return id[s];return id[s] = ++cnt;
}
vector<pair<int,ld>> G[110]; //用邻接表存图
ld dfs(int s, int fa, int t, ld ans){ //搜起点s到终点t的路径。fa是s的上一个点if(s == t)return ans; //到达终点for(auto now : G[s]){int v = now.first;ld w = now.second;if(v == fa) continue; //不回头ld now_ans = dfs(v, s, t, ans * w);if(now_ans > 0) return now_ans; //返回答案}return -1; //没搜到路径
}
int main(){int n, q; cin >> n >> q;while(n--){ld va, vb;string sa, sb, _; // _ 是 ‘=’cin >> va >> sa >> _ >> vb >> sb;G[get_id(sa)].push_back(make_pair(get_id(sb), vb)); //双向边G[get_id(sb)].push_back(make_pair(get_id(sa), 1.0 / vb));}while(q--){ld va;string sa, sb, _;cin >> va >> sa >> _ >> sb;auto ans = dfs(get_id(sa), -1, get_id(sb), va);if(ans > 0) printf("%.10Lf\n", ans); //注意long double的输出格式else printf("impossible\n");}return 0;
}
Java代码
import java.util.*;
public class Main {static Map<String, Integer> id = new HashMap<>();static int cnt = 0;static List<Pair<Integer, Double>>[] G = new ArrayList[110]; static int get_id(String s) {if (id.containsKey(s)) return id.get(s);cnt++;id.put(s, cnt);return cnt;} static double dfs(int s, int fa, int t, double ans) {if (s == t) return ans;for (Pair<Integer, Double> now : G[s]) {int v = now.first;double w = now.second;if (v == fa) continue;double now_ans = dfs(v, s, t, ans * w);if (now_ans > 0) return now_ans;}return -1;} public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), q = sc.nextInt();for (int i = 1; i <= Math.min(n+n, 101); i++) G[i] = new ArrayList<>();while (n-- > 0) {double va, vb;String sa, sb, e;va = sc.nextDouble();sa = sc.next();e = sc.next();vb = sc.nextDouble();sb = sc.next();G[get_id(sa)].add(new Pair<>(get_id(sb), vb));G[get_id(sb)].add(new Pair<>(get_id(sa), 1 / vb));}while (q-- > 0) {double va;String sa, sb, e;va = sc.nextDouble();sa = sc.next();e = sc.next();sb = sc.next();double ans = dfs(get_id(sa), -1, get_id(sb), va);if (ans > 0) System.out.printf("%.10f\n", ans);else System.out.println("impossible");}}
}
class Pair<A, B> {A first;B second; Pair(A first, B second) {this.first = first;this.second = second;}
}
Python代码
import sys
sys.setrecursionlimit(1000000)
id = {} #用字典把单位转为唯一的数字
cnt = 0
G = [[] for _ in range(200)] # 邻接表存图
def get_id(s):global cntif s in id: return id[s]cnt += 1id[s] = cntreturn cnt
def dfs(s, fa, t, ans):if s == t: return ansfor v, w in G[s]:if v == fa: continuenow_ans = dfs(v, s, t, ans * w)if now_ans > 0: return now_ansreturn -1
n, q = map(int, input().split())
for i in range(n):va, sa, _, vb, sb = input().split()va, vb = float(va), float(vb)u, v = get_id(sa), get_id(sb)G[u].append((v, vb))G[v].append((u, 1.0 / vb))
for i in range(q):va, sa, _, sb = input().split()va = float(va)u, v = get_id(sa), get_id(sb)ans = dfs(u, -1, v, va)if ans > 0: print(ans) else: print("impossible")
相关文章:

《算法竞赛·快冲300题》每日一题:“单位转换”
《算法竞赛快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 单…...

R语言13-R语言中的数据导入导出和批量导入
数据导入 CSV 文件: 使用 read.csv() 函数导入逗号分隔的文本文件。 data <- read.csv("data.csv")Excel 文件: 使用 readxl 包中的函数 read_excel() 导入 Excel 文件。 install.packages("readxl") # 安装 readxl 包&#…...

【Java】对象与类
【Java】对象与类 文章目录 【Java】对象与类1、学习背景2、定义&使用2.1 创建类2.2 创建对象 3、static关键字3.1 修饰变量3.2 修饰方法3.3 修饰代码块3.4 修饰内部类 4、this关键字5、封装特性5.1 访问修饰符5.2 包的概念 6、构造方法7、代码块7.1 普通代码块7.2 成员代码…...

视频尺寸缩小,一键批量剪辑,轻松制作精简版
大家好!在视频剪辑中,有时我们需要将大尺寸的视频缩小,以适应特定的需求和平台要求。为了帮助您轻松制作精简版视频,我们推出了一款全新的工具——视频尺寸缩小批量剪辑软件!让您一键批量将视频尺寸缩小,轻…...

leetcode做题笔记94. 二叉树的中序遍历
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 思路一:模拟题意 void inorder(struct TreeNode*root,int* ans,int *resSize) {if(!root){return ;}inorder(root->left,ans,resSize);ans[(*resSize)] root->val;inorder(root->right…...
UWB高精度人员定位系统源码,微服务+java+ spring boot+ vue+ mysql技术开发
工业物联网感知预警体系,大中小企业工业数字化转型需求的工业互联网平台 工厂人员定位系统是指能够对工厂中的人员、车辆、设备等进行定位,实现对人员和车辆的实时监控与调度的系统,是智慧工厂建设中必不可少的一环。由于工厂的工作环境比较…...

企业党建杂志企业党建杂志社企业党建编辑部2023年第4期目录
卷首语 坚持学思用贯通 知信行统一 (0001) 赵荣地 国企与国资《企业党建》投稿:cn7kantougao163.com 深入推进新时代党的建设的重大部署 (0004) 陈锋 国有企业推进中国式现代化建设的使命任务和实践路径 (0006) 蒋雪群 创新与实践 浅析国企党建与生产经营工作…...

ChatGPT + Flutter快速开发多端聊天机器人App
下载地址:ChatGPT Flutter快速开发多端聊天机器人App 下载地址:ChatGPT Flutter快速开发多端聊天机器人App...

ubuntu18.04复现yolo v8之最终章,realsenseD435i+yolo v8完美运行
背景:上一篇博客我们已经为复现yolov8配置好了环境,如果前面的工作顺利进行,我们已经完成了90%(学习类程序最难的是环境配置)。 接下来将正式下载yolov8的相关代码,以及进行realsenseD435i相机yolo v8的de…...

Python统计中文词频的四种方法
统计中文词频是Python考试中常见的操作,由于考察内容较多,因此比较麻烦,那么有没有好的方法来实现呢?今天,我们总结了四种常见的中文词频统计方法,并列出代码,供大家学习参考。 中文词频统计主…...

sql server 快速安装
目录标题 一、下载二、直接选择基本安装二、下载ssms(数据库图形化操作页面)三、开启sa账号认证(一)第一步:更改身份验证模式(二)第二步:启用 sa 登录四、开启tcp/ip 一、下载 下载…...

机器学习之损失函数
深度学习中常用的损失函数多种多样,具体选择取决于任务类型和问题的性质。以下是一些常见的深度学习任务和相应的常用损失函数: 分类任务: 交叉熵损失函数(Cross-Entropy Loss):用于二分类和多类别分类任务…...

nacos适配SqlServer、Oracle
继上文《nacos适配达梦、瀚高、人大金仓数据库及部分源码探究 》后补充nacos适配SqlServer、Oracle的贴码,主要区别是SqlServer、Oracle的分页SQL有点不一样,做个记录; SqlServer的分页有三种实现方式:offset /fetch next、利用ma…...

力扣:74. 搜索二维矩阵(Python3)
题目: 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返…...

CPU、MCU、MPU、SOC、SOCPC、概念解释之在嵌入式领域常听到的名词含义
CPU、MCU、MPU、SOC等几个在嵌入式领域学习过程中会涉及到的几个名词。我们来学习一下,资料从网上搜集的,有错的地方可以指出。。。 CPU、MCU、MPU、SOC、SOCPC、 1. CPU2. MPU3.MCUMPU和MCU的区别:4.SOC5. SoPC 1. CPU CPU,即中…...

每日两题 111二叉树的最小深度 112路径总和(递归)
111 题目 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:2示例 2&#x…...

实训笔记8.24
实训笔记8.24 8.24笔记一、Sqoop数据迁移工具1.1 Sqoop的基本概念1.2 Sqoop的基本操作1.2.1 命令语法1.2.2 list-databases1.2.3 list-tables1.2.3 eval1.2.4 import1.2.5 export1.2.6 导入 二、Flume日志采集工具2.1 数据采集的问题2.2 数据采集一般使用的技术2.3 扩展&#x…...

Linux下的系统编程——系统调用(五)
前言: 由操作系统实现并提供给外部应用程序的编程接口。(Application Programming Interface,API)。系统调用就是应用程序同系统之间数据交互的桥梁。 open/close函数 1.open函数: (1)int open(char *pathname, int flags) …...

动物体外受精手术VR模拟仿真培训系统保证学生及标本的安全
奶牛是养殖业主要的资源,因此保证奶牛的健康对养殖业的成功和可持续发展具有重要已用,奶牛有一些常见易发病,一旦处理不当,对奶牛业都会造成较大的经济损失,传统的奶牛手术培训实操难度大、风险高且花费大,…...

微信小程序|步骤条
步骤条是现代用户界面设计中常见的元素之一,它能够引导用户按照预定顺序完成一系列任务或步骤。在小程序中,实现步骤条可以为用户提供更好的导航和引导,使用户体验更加流畅和直观。本文将介绍如何在小程序中实现步骤条,并逐步展示实现的过程和关键技巧 目录 步骤条的作用及…...

如何才能设计出“好的”测试用例?
软件测试用例的设计质量直接影响到测试的完整性、有效性以及自动化测试的实施效果,是软件测试成功的重要保证,良好的软件测试用例对于提高测试的有效性和效率至关重要。那大家知道好的测试用例该怎么写吗?应该从哪几个方面来撰写呢࿱…...

DirectExchange直连交换机
目录 一、简介 二、使用步骤 三、demo 父pom文件 pom文件 配置文件 config 消费者 生产者 测试 一、简介 直连型交换机,根据消息携带的路由键将消息投递给对应队列。 大致流程,有一个队列绑定到一个直连交换机上,同时赋予一个路由…...

Shell 编程:探索 Shell 的基本概念与用法
目录 Shell 简介 Shell 脚本 Shell 脚本运行 Shell 变量 1、创建变量和赋值 2、引用变量 3、修改变量的值 4、只读变量 5、删除变量 6、环境变量 Shell 字符串操作 1、拼接字符串 2、字符串长度 3、字符串截取 Shell 数组 1、创建数组 2、访问数组元素 shell …...

【Git分支操作---讲解二】
Git分支操作---讲解二 查看分支创建分支切换分支修改分支切换分支合并分支合并分支【冲突】(只会修改主分支不会修改其他分支)什么时候会有冲突? 查看分支 创建分支 切换分支 修改分支 切换分支 合并分支 合并分支【冲突】(只会修改主分支不会修改其他分支) 什么时…...

vue2+qrcodejs2+clipboard——实现二维码展示+下载+复制到剪切板——基础积累
最近在写后台管理系统时,遇到一个需求就是要实现二维码的展示下载复制到剪切板。 效果图如下: 1.二维码展示下载功能——qrcodejs20.0.2 我是安装的qrcodejs20.0.2,指定了具体的版本号,也可以安装默认的当前稳定版本࿰…...

【PHP】echo 输出数组报Array to string conversion解决办法
代码: <?PHP echo "Hello World!";$demoName array("kexuexiong","xiong");echo "<pre>";var_dump($demoName);echo $demoName; print_r($demoName);echo "</pre>"; ?>输出结果࿱…...

Arduino驱动MiCS-4514气体传感器(气体传感器篇)
目录 1、传感器特性 2、控制器和传感器连线图 3、驱动程序...

marked在vue项目中改变超链接跳转方式和图片放大预览
marked在vue项目中改变超链接跳转方式和图片放大预览 这里我是另起一个js文件对marked的配置做了修改,参考如下 import marked from marked let renderer new marked.Renderer() const linkRenderer renderer.link const imgRenderer renderer.image // 超链接…...

leetcode485. 最大连续 1 的个数
思路:【双指针】 left左边界,right往右跑遇到0,则计算该长度。并更新cnt(最大连续1个数)。 class Solution { public:int findMaxConsecutiveOnes(vector<int>& nums) {int left 0, right 0;int cnt 0;…...

linux 源代码编译
源代码编译 有时候会在linux上下载源码包,然后进行编译成可执行的文件,这个过程需要经过configure、make、make install、make clean四个步骤 configure 为这个程序在当前的操作系统环境下选择合适的编译器和环境参数来编译该代码 make 对程序代码进行编…...