洛谷 P9914 题解
P9914 「RiOI-03」匀速相遇 题解
(使用umap的暴力非正解)
「RiOI-03」匀速相遇
题目背景
当大家都在加速时,我与你,在人生中的十字路口,匀速地相遇了。
确是惊动我心的一瞥,却是无法逗留的遗憾,我们再次,朝着自己的方向匀速奔跑。下次再见,又会是什么时候呢……
题目描述
平面直角坐标系上有 个点,其中:
-
有 个 类点,它们在初始时依次位于位置 。
-
有 个 类点,它们在初始时依次位于位置 。
在某一个时刻, 类点同时开始运动。具体地:
-
对于第 个 类点,其以 个单位长度每秒的速度向上(即 轴正方向)匀速运动。特别地,若 ,则该点始终保持静止。
-
对于第 个 类点,其以 个单位长度每秒的速度向右(即 轴正方向)匀速运动。特别地,若 ,则该点始终保持静止。
相遇与分离实在是再平凡不过的了。作为匆匆时光里的一名过客,在这个你暂留的驿站里,你能否帮小 T 解决这个简单的问题:求出有多少点对会在某个时刻相遇,即它们在某一刻共点。
由于你无法使时间静止,所以所有点无论相遇与否,都会永无止境地运动下去。祝愿在这道路上奔跑的你,能有一天与理想匀速相遇,永不停息。
输入格式
第一行两个正整数 。
第二行 个整数 ,依次表示第 个 类点的运动速度。
第三行 个整数 ,依次表示第 个 类点的运动速度。
数据规模与约定
本题开启捆绑测试。
-
Subtask 0(10 pts):,。
-
Subtask 1(20 pts):,。
-
Subtask 2(30 pts):保证 ,。
-
Subtask 3(40 pts):无特殊限制。
对于所有数据,,。
题解
学oi这么多月了第一次场切黄题(尽管不会哈希做法用的是侥幸没被出题人卡掉的umap),所以打算写篇题解,顺带着测试一下自己blog的可用性(反正也没有人看)(连LaTeX都不支持可用个鬼啊)
根据题面,假设两个点在第秒相遇,则编号为的类点在第秒时的坐标为,编号为的类点在第秒时的坐标则为。显然,当同时满足且时,两点能在第秒相遇。可以把上式变形为。
到这里就是第一个坑点了,t不一定是一个整数,所以不能直接计算和的值,c++中除法的自动取整会把两个互不相等的取成同一个整数。于是可以想到把等式两边同时乘以,得到,由于的上界为,不能直接开数组存储数据,所以直接开umap在输入时记录每个出现的次数,在输入时直接求解即可。由于umap查询操作时间复杂度是一个常数,所以时间复杂度近似为,可以通过本题,不过最慢的点达到了800ms,对于的数据范围还是显得太久了,正解的哈希做法应该会快一些。
另外男酿神犇@kamisako提出了一种复杂度为的做法:离散化之后桶排,但我不会离散化,所以细节可以问他。
另外还需要注意一个特判,当或时点或会永远静止,无法与任何一个点相遇,所以输入时遇到直接continue即可。
代码
1 |
|