题解：AT_pakencamp_2025_day1_c 2nd Larger

小屹0_0 · 2026-05-14 16:21:40 · 题解

首先，我们考虑到重复元素没有任何贡献，直接扔了，去重。

接下来，我们依次考虑每一个 a_i，去考虑他对应了哪些 b_i，分别得到了什么结果。

有一个显然的事情：我们将每一个 a_i 对应的最大的 a_i b_j 和第二大的 a_i b_j 扔进一个集合，我们的答案一定也是这个集合的第二大的数。

那么我们继续观察，发现，对于每一个 a_i，其对应的最大的 a_i b_j 和第二大的 a_i b_j 一定选自，a_i 乘上最大的 b_j，第二大的 b_j，最小的 b_j，第二小的 b_j。

那么做法就是：对于每一个 a_i，将他与最大，第二大，最小，第二小的 b_j 相乘扔进一个不可重集合，最后答案就是第二大的那个。

实现使用 set，以及还记得那个让你十年 OI 一场空的东西吗？

代码如下。

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

#define ll long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;

namespace ARIS0_0{
    int n, m;
    ll a[N], b[N];

    void init(){
    }
    void solve(){
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        for (int i = 1; i <= m; i ++ ) cin >> b[i];

        sort(a + 1, a + n + 1);
        sort(b + 1, b + m + 1);
        n = unique(a + 1, a + n + 1) - a - 1;
        m = unique(b + 1, b + m + 1) - b - 1;

        set <ll> s;
        for (int i = 1; i <= n; i ++ ){
            for (int j = 1; j <= min(m, 2); j ++ ) s.insert(a[i] * b[j]);
            for (int j = m; j >= max(m - 1, 1); j -- ) s.insert(a[i] * b[j]);
        }

        if (s.size() < 2){
            cout << "None\n";
            return ;
        }
        cout << (*prev(prev(s.end()))) << "\n";
    }
    void single(){ init(), solve(); }
    void multi(){ init(); int T; cin >> T; while (T -- ) solve(); }
    void idmulti(){ init(); int id, T; cin >> id >> T; while (T -- ) solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::multi();
}