洛谷 P9914 题解

学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;
}