标题

黑洞题解

思路

对于每一个维度，会有正反两个方向。总共有 $2^n$ 种方法，确定他的对角线长度取决于所有维度的最小值。所以找到最小值就有一半的方法的答案贡献是最小值，也就是 $2^{n-1}$ 。再找次小值，以此类推。 特别的，当取到两个同维度的，则不需要取一半。

解题方法

使用 $xp$ 数组记录 $2^n$ 对 $mod$ 取余的结果。再存储每一个方向的长度，记录维度，排序。

复杂度

时间复杂度:

$O(nlogn)$

空间复杂度:

$O(n)$

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool b[1000030];
const int mod=1e9+7;
int n,m[1000030],a[1000030],xp[1000030];
struct node{
	int sum,num;
};
bool cmp(node x,node y){
	return x.sum<y.sum;
}
vector<node> v;
signed main(){
//	freopen("hole7.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i];
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v.push_back({a[i]-1,i});
		v.push_back({m[i]-a[i],i});
	}
	sort(v.begin(),v.end(),cmp);
	xp[0]=1;
	for(int i=1;i<=n;i++){
		xp[i]=xp[i-1]*2;
		xp[i]%=mod;
	}
	int idx=n,sum=0;
	for(auto i:v){
		if(b[i.num]){
			sum+=i.sum*xp[idx];
			sum%=mod;
			break;
		}
		else{
			idx--;
			b[i.num]=1;
			sum+=i.sum*xp[idx];
			sum%=mod;
		}
	}
	cout<<(sum+1)%mod;
}

标题

大标题大标题大标题大标题

思路

考虑暴力，对于每个方向，先求出它向正、负延伸的范围，再 $O(2^n)$ 计算向正还是负延伸。

优化，发现每一次能延伸多少只看其中最小的，而且顺序不影响答案，所以可以按向正、负延伸的范围的最小值排序，一旦后面的最小值都比当前最小值还大，再搜索没有意义，直接加上后面总共的贡献返回即可。
做完后看了一眼数据范围，$2e5$能过，奇迹啊

时间复杂度:

$O(2^n)$

十年OI一场空，不开long long见祖宗

$AC$ $Code$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
const int Mod=1e9+7;
int n,m[N],mi[N]={1};
struct node{
	int x,y;
}a[N];
int h[N];
int ans=1;
void dfs(int x,int minn){
	if(x==n+1){
		ans+=minn;
		ans%=Mod;
		return;
	}
	if(minn<=h[x]){
		ans+=minn*mi[n-x+1]%Mod;
		ans%=Mod;
		return;
	}
	dfs(x+1,min(minn,a[x].x));
	dfs(x+1,min(minn,a[x].y));
}
bool cmp(node A,node B){
	return min(A.x,A.y)<min(B.x,B.y);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		mi[i]=mi[i-1]*2%Mod;
		cin>>m[i];
	}
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		a[i].x=m[i]-x;
		a[i].y=x-1;
	}
	sort(a+1,a+1+n,cmp);
	h[n+1]=1e18;
	for(int i=n;i>=1;i--){
		h[i]=min(h[i+1],min(a[i].x,a[i].y));
	}
	dfs(1,1e18);
	cout<<ans;
}

暴力卍岁！！！（佛教，申和注意一下）

显然，每一维有两个方向，所以 $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;
}