[Algo Beat Contest 001 D] Dreamed Sequence 官方题解

joe_zxq · 2024-11-10 21:27:30 · 题解

显然最终的序列中 x 最多出现的次数为 \sum\limits_{i=1}^{10^9}\sum\limits_{j=1}^{10^9}\min(c_i,d_j)[i \times j \mod M=x]，其中 c_t,d_t 分别表示 t 在序列 A,B 种出现的次数。

虽然序列元素的数据范围很大，但是一个序列中的不同元素显然最多只有 N 个。考虑分别处理出两个序列的不同元素即它们分别的出现次数。于是乎只需要考虑存在于序列中的的 i,j 按上述式子计算即可。

时间复杂度：O(N^2)。

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll mod = 1e9 + 7;

ll n, x, y, ans, a[114514], b[114514];
unordered_map<ll, ll> cnt, mp;
set<ll> s;
pair<ll, ll> c[114514], d[114514];

ll op(ll t[], pair<ll, ll> p[], ll tot = 0) {
    s.clear();
    cnt.clear();
    for (ll i = 1; i <= n; i++) {
        cin >> t[i];
        cnt[t[i]]++;
    }
    for (ll i = 1; i <= n; i++) {
        s.insert(t[i]);
    }
    for (ll kk : s) {
        tot++;
        p[tot] = {kk, cnt[kk]};
    }
    return tot;
}

void solve() {
    cin >> n;
    x = op(a, c);
    y = op(b, d);
    for (ll i = 1; i <= x; i++) {
        for (ll j = 1; j <= y; j++) {
            mp[c[i].first * d[j].first % mod] += min(c[i].second, d[j].second);
        }
    }
    for (pair<ll, ll> kk : mp) {
        ans = max(ans, kk.second);
    }
    cout << ans;
}

int main() {

    solve();

    return 0;
}