题解：P11214 【MX-J8-T2】黑洞

20 Oct, 2024 11:28 PM +08:00

非常难的一道题，想了 $150$ 分钟。（ 怎么降黄了

根据题意，对每一维同时增加或减少一个正整数 $C$，能得到被黑洞吞噬的点 $A$。

把每一维对应成一根竹竿，表示 能够增减的范围，以 样例 #3 为例：

方便起见，调换这些竹竿的方向，把距离 $0$ 较长的一端放在上面，按另一端的长度排序。

因为有竹竿 $[3, -1]$ ，所以 $C \leq 3$，那么对于所有竹竿，绝对值大于 $3$ 的部分是没用的。

也就是说，对于所有输入，可以转化成 $n$ 个竹竿，其中第 $i$ 个竹竿 上端长度为 $L$，下端长度为 $x_i$，保证 $x_{i-1} \le x_i$ 且 $x_i \le L$ 。

考虑第 $i$ 个竹竿对 $A$ 取值数量的贡献 $p_i$ ，可以写成： $$p_i = 2^{n - i + 1}(x_i-x_{i-1})$$ 答案是 $1 + \Sigma {p} + (L-x_n)$ ，其中 $1$ 是输入的点本身，$L-x_n$ 是 $C > x_n$ 的情况 。

时间复杂度 $O(n \log n)$ ，瓶颈在排序，代码不难写：

#include <bits/stdc++.h>
#define u64 unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
#define i64 long long

const i64 MAXN = 2e5 + 64;

const i64 MOD = 1000000007;
#define mod(x) ((x) % MOD)

i64 m[MAXN], a[MAXN], n;

i64 x[MAXN], L = inf, sigp;

void solve()
{
    assert(scanf("%lld", &n));
    for (i64 i = 1; i <= n; ++i) assert(scanf("%lld", &m[i]));
    for (i64 i = 1; i <= n; ++i) assert(scanf("%lld", &a[i]));
    for (i64 i = 1, l; i <= n; ++i)
    {
        l = m[i] - a[i], x[i] = a[i] - 1;
        if (l < x[i]) std::swap(l, x[i]);
        L = std::min(L, l);
    }
    for (i64 i = 1; i <= n; ++i) x[i] = std::min(L, x[i]);
    std::sort(x + 1, x + 1 + n, std::less<i64>());
    for (i64 i = n, k = 2; i; --i, k = mod(k << 1))
    {
        sigp = mod(sigp + (x[i] - x[i - 1]) * k);
    }
    printf("%lld\n", mod(1 + sigp + (L - x[n])));
}

signed main()
{
    solve();
    return 0;
}

本文最初发表于 Luogu，于 2026-04-19 同步至本站。

题面： https://www.luogu.com.cn/problem/P11214