P11214 【MX-J8-T2】黑洞

水星湖 · 2024-10-21 22:27:46 · 题解

赛前没仔细想觉得是绿的，现在还是建议黄吧。

显然，每一维有两个方向，所以 n 维一共有 2^n 个方向。所求即为对于 2^n 个方向中的每一种方向，最大的合法 k 之和。

直接枚举复杂度为 \mathcal O(2^n) 或 \mathcal O(n2^n)，考虑优化，假设有一维的某一个方向最大的合法 k 非常小，那么确定这一维之后，剩下 n-1 维的 2^{n-1} 种情况的贡献都会为这一维的 k，这启发我们对每一维的每一个方向拆贡献计算。

我们希望当前的 k 是所有方向的最小值，所以可以按照每一维，每个方向的最大合法 k 共 2n 个数从小到大排序，然后倒序处理。考虑我们枚举到这个数是维度 x 的某一个方向的最大合法 k，显然，如果到此时出现过的不同的维度（含 x）小于 n 个，则说明当前数不可能作为最小值，所以没有贡献，否则，答案加上这个数乘以这个数的贡献系数即可。假设这个数后面有 y 个维度出现了两次（含这个数所在的维度），则贡献系数为 2^y，这个可以在倒序枚举时计算出来，只要维护一个 t 表示贡献系数，在一个维度第二次出现时令 t\gets t\times 2 即可。

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

const int N = 4e5 + 5, mod = 1e9 + 7;
int n, a[N], f[N];
pair<int, int> b[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1, x; i <= n; i++) {
        cin >> x;
        b[i] = {x - 1, i}, b[n + i] = {a[i] - x, i};
    }
    sort(b + 1, b + 2 * n + 1); 
    int t = 1, ans = 1, cnt = 0;
    for(int i = 2 * n; i >= 1; i--) {
        auto [v, id] = b[i];
        cnt += !f[id];
        if(cnt == n) ans = (ans + 1ll * t * v % mod) % mod;
        if(f[id]) t = t * 2 % mod;
        f[id] = 1;
    }
    cout << ans << '\n';
    return 0;
}