「RiOI-03」匀速相遇 题解

cff_0102 · 2023-12-09 17:13:51 · 题解

假设第 i 个 A 类点和第 j 个 B 类点会在第 t 秒在 (i,j) 相遇，则必须满足 t\times a_i=j,t\times b_j=i，故 t=\dfrac{j}{a_i}=\dfrac{i}{b_j}（这里暂且假设 a_i,b_j 不为 0），再交叉相乘得到 i\times a_i=j\times b_j。

所以只需要在输入数组 a 时记下所有 i\times a_i，然后在输入数组 b 的时候看看有几个 i 满足 i\times a_i=j\times b_j（有几个 i 满足这个等式，就有几个 A 类点会和这个 B 类点相遇），最后再加到记录答案的变量 s 上。

不要忘了特判 a_i=0 和 b_j=0 的情况，此时这个点原地不动，也不可能和其它点相遇。

#include<bits/stdc++.h>
using namespace std;
int a[1145141],b[1145141];
unordered_map<long long,int> ai;
int main(){
    ios::sync_with_stdio(false);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=0){
            long long temp=1ll*i*a[i];
            ai[temp]++;//ai[temp] 存的是满足 i*a_i=temp 的 i 的个数
        }
    }
    long long s=0;
    for(int j=1;j<=m;j++){
        cin>>b[j];
        if(b[j]!=0){
            long long temp=1ll*j*b[j];
            if(ai.count(temp)){//如果有 i 满足 i*a_i=j*b_j
                s+=ai[temp];//则将满足等式的 i 的个数加到答案中
            }
        }
    }
    cout<<s;
    return 0;
}