自动搬运

查看原文

来自洛谷，原作者为

	LiuCarry 只可惜没有如果。

搬运于2025-08-24 23:05:21，当前版本为作者最后更新于2024-10-20 16:58:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}