P9914 题解

FurippuWRY · 2023-12-09 18:04:00 · 题解

样例给的提示比较少，于是自己造了一些。

设点的速度为 v。

设有点 A(2,0),B(3,0),C(0,6)，它们的速度分别为 v_A=3,v_B=2,v_C=1，A 与 C，B 与 C 都可以相遇，发现一点：v_A \times x_A=v_B \times x_B=v_C \times y_C=6。

于是可以推测：对于 \text{A} 类点，设 p=x\times v_\text A；对于 \text{B} 类点，设 q=y\times v_\text B。如果 p=q，那么它们可以相遇。

知道了这一点，那么就可以把每个点的横坐标或纵坐标乘上对应的速度，并寻找相等结果的个数，输出即可。

但是 O(nm) 的暴力枚举肯定不行，n,m\in[1,10^6]，会超时。这时可以用 multiset 开一个集合，存储值不为 0 的 a_i\times v_{a_i}（若值为 0，那么它根本动不了，就不用存进去），然后查找与 b_i\times v_{b_i} 的值相同的元素个数，并且累加，最后输出即可。

需要稍微卡一下常，我这份代码能过，但有时候因为评测机的问题，会超 0.01~0.03s，可以打个快读快写优化一下。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, m, a, b, ans = 0;
multiset<ll> x;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i) {
        cin >> a;
        a *= i;//横坐标乘速度
        if (a != 0) x.insert(a);//若不为 0，则加入集合中
    }
    for (ll i = 1; i <= m; ++i) {
        cin >> b;
        b *= i;//纵坐标乘速度
        ans += x.count(b);//统计相等元素的个数。
    }
    cout << ans;

    return 0;
}