专栏文章

「C.E.L.U-03」重构 题解

潘潘德理2010
P7840题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minmxajx
此快照首次捕获于
2025/12/02 05:01
3 个月前
此快照最后确认于
2025/12/02 05:01
3 个月前
查看原文
看着没有人用 wqs 二分做，就写一篇题解吧。
首先，通过 Prufer 序列，我们知道，对于任意一个长度为 nn 的序列 dd 满足 di∈[1,n−1],∑d=2n−2d_i\in [1,n-1],\sum d=2n-2，都能构建一棵树。
也就是说题目转化成了：
给定长为 nn 的序列 vv，构造长为 nn 的序列 dd 满足 di∈[1,n−1],∑d=2n−2d_i\in [1,n-1],\sum d=2n-2，最小化 ∑di2vi\sum d_i^2v_i 的值。
直接 dp 肯定是不行的，复杂度不能接受。
观察到有 ∑d=2n−2\sum d=2n-2 的限制，处理这种限制的利器就是 wqs 二分。
wqs 二分的实现
二分每个度数的惩罚值 tt。对于每个 ii，将 did_i 设为满足 di∈[1,n−1]d_i\in[1,n-1] 且使 di2vi−tdid_i^2v_i-td_i 取到最小值的 did_i（可以使用二次函数的知识求出），然后根据 ∑d\sum d 与 2n−22n-2 的大小关系调整 tt。
凸性的感性证明
因为答案是关于每个 did_i 的二次函数之和，随着 ∑d\sum d 的增大，答案的增加速度会越来越快，所以有凸性。
代码CPP
#include<bits/stdc++.h>
#define int __int128
using namespace std;
typedef long long ll;
int n,a[300010];
int f[300010],cnt[300010];
int w(int as,int x,int at){
	return (as*x-at)*x;
}
void re(int &x){
	if(x<=1) x=1;
	if(x>=n-1) x=n-1;
}
int read(){
	ll x;
	cin>>x;
	return x;
}
void pr(int x){
	ll y=x;
	cout<<y<<" ";
}
int div(int x,int y){
	int p=(x%y+y)%y;
	x-=p;
	return x/y;
}
void ret(int at){
	memset(f,0,sizeof(f));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++){
		int u=div(at,2*a[i]);
		int v=u+1;
		re(u);
		re(v);
		int uc=w(a[i],u,at);
		int vc=w(a[i],v,at);
		if(vc<=uc){
			f[i]=f[i-1]+vc;
			cnt[i]=cnt[i-1]+v;
		}
		else{
			f[i]=f[i-1]+uc;
			cnt[i]=cnt[i-1]+u;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	int le=-1e9,ri=1e9,mid;
	while(le<ri){
		mid=(le+ri)>>1;
		ret(mid);
		if(cnt[n]>=2*n-2) ri=mid;
		else le=mid+1;
	}
	ret(le);
	pr(f[n]+(2*n-2)*le);
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...