洛谷 P9914 题解

P9914 「RiOI-03」匀速相遇 题解
（使用umap的暴力非正解）

「RiOI-03」匀速相遇

题目背景

当大家都在加速时，我与你，在人生中的十字路口，匀速地相遇了。

确是惊动我心的一瞥，却是无法逗留的遗憾，我们再次，朝着自己的方向匀速奔跑。下次再见，又会是什么时候呢……

题目描述

平面直角坐标系上有 $n + m$ 个点，其中：

• 有 $n$ 个 $\rm A$ 类点，它们在初始时依次位于位置 $(1, 0), (2, 0), (3, 0), \dots, (n, 0)$。

• 有 $m$ 个 $\rm B$ 类点，它们在初始时依次位于位置 $(0, 1), (0, 2), (0, 3), \dots, (0, m)$。

在某一个时刻，$\rm A, B$ 类点同时开始运动。具体地：

• 对于第 $i$ 个 $\rm A$ 类点，其以 $a_i$ 个单位长度每秒的速度向上（即 $y$ 轴正方向）匀速运动。特别地，若 $a_i = 0$，则该点始终保持静止。

• 对于第 $i$ 个 $\rm B$ 类点，其以 $b_i$ 个单位长度每秒的速度向右（即 $x$ 轴正方向）匀速运动。特别地，若 $b_i = 0$，则该点始终保持静止。

相遇与分离实在是再平凡不过的了。作为匆匆时光里的一名过客，在这个你暂留的驿站里，你能否帮小 T 解决这个简单的问题：求出有多少点对会在某个时刻相遇，即它们在某一刻共点。

由于你无法使时间静止，所以所有点无论相遇与否，都会永无止境地运动下去。祝愿在这道路上奔跑的你，能有一天与理想匀速相遇，永不停息。

输入格式

第一行两个正整数 $n, m$。

第二行 $n$ 个整数 $a_1\dots a_n$，依次表示第 $1\dots n$ 个 $\rm A$ 类点的运动速度。

第三行 $m$ 个整数 $b_1\dots b_m$，依次表示第 $1\dots m$ 个 $\rm B$ 类点的运动速度。

数据规模与约定

本题开启捆绑测试。

• Subtask 0（10 pts）：$n \leq 10$，$m \leq 10$。

• Subtask 1（20 pts）：$n \leq 5\times 10^3$，$m \leq 5\times 10^3$。

• Subtask 2（30 pts）：保证 $\forall a_i \geq 1$，$\forall b_i \geq 1$。

• Subtask 3（40 pts）：无特殊限制。

对于所有数据，$1 \leq n, m \leq 10^6$，$0 \leq a_i, b_i \leq 10^9$。

题解

学oi这么多月了第一次场切黄题（尽管不会哈希做法用的是侥幸没被出题人卡掉的umap），所以打算写篇题解，顺带着测试一下自己blog的可用性（反正也没有人看）（连LaTeX都不支持可用个鬼啊）

根据题面，假设两个点在第$t$秒相遇，则编号为$i$的$A$类点在第$t$秒时的坐标为$(i,a_i\cdot t)$，编号为$j$的$B$类点在第$t$秒时的坐标则为$(b_j\cdot t,j)$。显然，当同时满足$i=b_j\cdot t$且$j=a_i\cdot t$时，两点能在第$t$秒相遇。可以把上式变形为$t=\frac {i} {b_j}=\frac {j} {a_i}$。

到这里就是第一个坑点了，t不一定是一个整数，所以不能直接计算$\frac {i} {b_j}$和$\frac {j} {a_i}$的值，c++中除法的自动取整会把两个互不相等的$t$取成同一个整数。于是可以想到把等式两边同时乘以$b_j\cdot a_i$，得到$i\cdot a_i=j\cdot b_j$，由于$i\cdot a_i$的上界为$10^6\times 10^9 = 10^{15}$，不能直接开数组存储数据，所以直接开umap在输入$a_i$时记录每个$i\cdot a_i$出现的次数，在输入$b_j$时直接求解即可。由于umap查询操作时间复杂度是一个常数，所以时间复杂度近似为$O(k(n+m))$，可以通过本题，不过最慢的点达到了800ms，对于$n+m\leq 2\times10^6$的数据范围还是显得太久了，正解的哈希做法应该会快一些。

另外男酿神犇@kamisako提出了一种复杂度为$O(nlogn)$的做法：离散化之后桶排，但我不会离散化，所以细节可以问他。

另外还需要注意一个特判，当$a_i$或$b_j=0$时点$i$或$j$会永远静止，无法与任何一个点相遇，所以输入时遇到$0$直接continue即可。

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
unordered_map <ll,int> leg; //a(i)*i出现的次数
ll read(){}//快读，此处略去
ll a,b;
signed main(){
    int n,m;
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a=read();
        if(a<=0) continue; //特判
        leg[a*i]++;
    }
    int cnt = 0;
    for(int j=1;j<=m;j++){
        b=read();
        if(b<=0) continue;
        cnt+=leg[b*j];
    }
    printf("%d",cnt);
    return 0;
}