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

· · 题解

52pts

我们可以将空间分为 2^n 份，每份是以黑洞为原点的坐标系的每个坐标轴的半轴的交集，半轴可以取正或负，因此是 2^n 份。

这样枚举每个坐标 i，答案就是对每一份，每个方向上到边界的距离的最小值的和，即 \min{(a_i-1)} 或 \min{(m_i-a_i)}，时间复杂度 O(2^n \times n)。

100pts

然后考虑每个 i 对答案的贡献。

我们先把 a_i-1 和 m_i-a_i 列出来，比如对于这个样例：

3
5 7 8
4 5 2

我们把它写成：

3 1
4 2
1 6

第一个是 a_i-1，第二个是 m_i-a_i，我们分别称他们为 x_i 和 y_i。

这样的话答案就是每一个 i 取 x_i 或 y_i 的这一个路径上的最小值和，因此只有一个从上到下的路径的最小值可以对答案产生贡献。

我们将 x_i 和 y_i 合起来，排个序，发现贡献就是 num \times 2^{cnt}，其中 num 是当前枚举到的数，cnt 是 x_i 和 y_i 都没有被取到的 i 的个数，即 x_i 和 y_i 都大于 num 的 i 的个数。还有别忘了开 long long 和初始时令 ans=1。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n;
int m[200005];
int a[200005];
int ans=1;
vector<pair<int,int>> vec;
int cnt[200005];
bool bo=0;
int cnt2;
int qpow(int x,int y)
{
    if(y==0) return 1;
    if(y==1) return x;
    int res=qpow(x,y>>1);
    return y&1?(res*res%mod*x%mod):(res*res%mod);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>m[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    vec.resize(2*n);
    for(int i=1;i<=n;i++)
    {
        vec[2*(i-1)]={a[i]-1,i};
        vec[2*(i-1)+1]={m[i]-a[i],i};
        cnt[i]=2;
    }
    cnt2=n;
    sort(vec.begin(),vec.end());
    int num,I;
    for(int i=0;i<2*n&&!bo;i++)
    {
        num=vec[i].first;
        I=vec[i].second;
        cnt[I]--;
        if(!cnt[I]) bo=1;
        if(cnt[I]) cnt2--;
        int res=num*qpow(2,cnt2)%mod;
        ans=(ans+res)%mod;
    }
    cout<<ans;
    return 0;
}