题解：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 同步至本站。