差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/13 21:50]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/24 17:22] (当前版本)
jxm2001 [例题四]
@@ 行 93: / 行 93: @@
 	}
 	enter(solve(n,m,ans).first+ans*k);
+	return 0;
+}
+</code>
+</hidden>
+==== 例题二 ====
+[[https://codeforces.com/group/2g1PZcsgml/contest/340322/problem/M|gym102059 M]]
+=== 题意 ===
+给定一棵边权树，要求从树上选 $k$ 条边，所有边无公共点且最大化边权和。
+=== 题解 ===
+设 $F(x)$ 表示选 $x$ 条边的最大边权和，不难发现 $F(x)$ 为凸函数。斜率最大值为 $V$(无脑加一条边)，最小值为 $-nV$(强行加一条边的最坏影响)。
+利用 $\text{wqs}$ 二分套树形 $\text{dp}$ 求解即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2.5e5+5,MAXV=1e6+5;
+const LL inf=1e18;
+struct Edge{
+	int to,next;
+	LL w;
+	Edge(int to=0,LL w=0,int next=0){
+		this->to=to;
+		this->w=w;
+		this->next=next;
+	}
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge(v,w,head[u]);
+	head[u]=edge_cnt;
+}
+struct Node{
+	LL s;
+	int cnt;
+	Node(LL s=0,int cnt=0){
+		this->s=s;
+		this->cnt=cnt;
+	}
+	bool operator < (const Node &b)const{
+		return s<b.s||(s==b.s&&cnt<b.cnt);
+	}
+	Node operator + (const Node &b)const{
+		return Node(s+b.s,cnt+b.cnt);
+	}
+	void operator += (const Node &b){
+		s+=b.s;
+		cnt+=b.cnt;
+	}
+	Node operator - (const Node &b)const{
+		return Node(s-b.s,cnt-b.cnt);
+	}
+};
+Node dp[MAXN][2];
+void dfs(int u,int fa){
+	dp[u][0]=Node(0,0);
+	dp[u][1]=Node(-inf,0);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u);
+		dp[u][0]+=max(dp[v][0],dp[v][1]);
+	}
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dp[u][1]=max(dp[u][1],dp[u][0]-max(dp[v][0],dp[v][1])+dp[v][0]+Node(edge[i].w,1));
+	}
+}
+Node solve(int n,LL k){
+	_rep(i,1,edge_cnt)
+	edge[i].w-=k;
+	dfs(1,0);
+	Node ans=max(dp[1][0],dp[1][1]);
+	_rep(i,1,edge_cnt)
+	edge[i].w+=k;
+	return ans;
+}
+int main(){
+	int n=read_int(),k=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int(),w=read_int();
+		Insert(u,v,w);
+		Insert(v,u,w);
+	}
+	LL lef=-1LL*MAXV*n,rig=MAXV,ans;
+	if(solve(n,lef).cnt<k){
+		puts("Impossible");
+		return 0;
+	}
+	while(lef<=rig){
+		LL mid=lef+rig>>1;
+		if(solve(n,mid).cnt>=k){
+			ans=mid;
+			lef=mid+1;
+		}
+		else
+		rig=mid-1;
+	}
+	enter(solve(n,ans).s+ans*k);
+	return 0;
+}
+</code>
+</hidden>
+==== 例题三 ====
+[[https://www.luogu.com.cn/problem/CF739E|CF739E]]
+=== 题意 ===
+一共有 $n$ 只宝可梦，有 $a$ 个普通球和 $b$ 个高级球。每个宝可梦在一次捕捉失败后就会逃跑。
+对第 $i$ 只宝可梦，用普通球的捕获率是 $p_i$，用高级球的捕获率是 $q_i$，同时用普通球和高级球的捕获率是 $p_i+q_i-p_iq_i$。
+求最优策略下能捕捉宝可梦的期望值。
+=== 题解 ===
+设 $F(x,y)$ 表示用 $x$ 个普通球和 $y$ 个高级球的期望捕捉数。
+不难发现对固定的 $x$，$F(x,y)$ 是凸函数，于是利用 $\text{wqs}$ 二分可以 $O(n\log v)$ 计算出 $F(x,b)$。
+然后显然 $F(x,b)$ 也是凸函数，于是再套一层 $\text{wqs}$ 二分可以 $O\left(n\log^2 v\right)$ 计算出 $F(a,b)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e3+5;
+const double eps=1e-8;
+struct Node{
+	double s;
+	int cnt1,cnt2;
+	Node(double s=0.0,int cnt1=0,int cnt2=0){
+		this->s=s;
+		this->cnt1=cnt1;
+		this->cnt2=cnt2;
+	}
+	void operator += (const Node &b){
+		s+=b.s;
+		cnt1+=b.cnt1;
+		cnt2+=b.cnt2;
+	}
+	bool operator < (const Node &b)const{
+		return s<b.s;
+	}
+};
+int n,a,b;
+double p[MAXN],q[MAXN],r[MAXN];
+Node dp[MAXN];
+Node solve2(double k1,double k2){
+	Node ans=Node(0,0,0);
+	_rep(i,1,n)
+	ans+=max({Node(0,0,0),Node(p[i]-k1,1,0),Node(q[i]-k2,0,1),Node(r[i]-k1-k2,1,1)});
+	return ans;
+}
+Node solve(double k){
+	double lef=0,rig=1;
+	while(rig-lef>eps){
+		double mid=(lef+rig)/2;
+		if(solve2(k,mid).cnt2>=b)
+		lef=mid;
+		else
+		rig=mid;
+	}
+	Node t=solve2(k,lef);
+	t.s+=lef*b;
+	return t;
+}
+int main(){
+	n=read_int(),a=read_int(),b=read_int();
+	_rep(i,1,n)
+	scanf("%lf",&p[i]);
+	_rep(i,1,n)
+	scanf("%lf",&q[i]);
+	_rep(i,1,n)
+	r[i]=p[i]+q[i]-p[i]*q[i];
+	double lef=0,rig=1;
+	while(rig-lef>eps){
+		double mid=(lef+rig)/2;
+		if(solve(mid).cnt1>=a)
+		lef=mid;
+		else
+		rig=mid;
+	}
+	printf("%.6lf",solve(lef).s+lef*a);
+	return 0;
+}
+</code>
+</hidden>
+==== 例题四 ====
+[[https://www.luogu.com.cn/problem/P4983|洛谷p4983]]
+=== 题意 ===
+给定序列 $A$，定义子串 $A[l\sim r]$ 的费用为 $(\sum_{i=l}^r a_i+1)^2$。要求将 $A$ 划分成 $m$ 段，最小化费用。
+=== 题解 ===
+$\text{wqs}$ 二分套斜率优化，斜率优化的难点在于 $\text{wqs}$ 二分具有第二关键字，即收益相同的情况下需要最大或最小化划分的次数。
+斜率优化比较难处理这方面的要求。本人的斜率优化板子貌似是强制取最小的，如果  $\text{WA}$  了可以考虑假设强制取最小的/最大都试试。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+const LL inf=1e18;
+int s[MAXN],cnt[MAXN],q[MAXN];
+LL dp[MAXN];
+LL caly(int pos){
+	return 1LL*s[pos]*(s[pos]-2)+dp[pos];
+}
+double slope(int i,int j){
+	return 1.0*(caly(i)-caly(j))/(s[i]-s[j]);
+}
+pair<LL,int> solve(int n,LL k){
+	int head=0,tail=-1;
+	q[++tail]=0;
+	_rep(i,1,n){
+		while(head<tail&&slope(q[head],q[head+1])<2*s[i])head++;
+		dp[i]=dp[q[head]]+1LL*(s[i]-s[q[head]]+1)*(s[i]-s[q[head]]+1)-k;
+		cnt[i]=cnt[q[head]]+1;
+		while(head<tail&&slope(q[tail],i)<slope(q[tail-1],q[tail]))tail--;
+		q[++tail]=i;
+	}
+	return make_pair(dp[n],cnt[n]);
+}
+int main()
+{
+	int n=read_int(),m=read_int();
+	_rep(i,1,n)
+	s[i]=read_int()+s[i-1];
+	LL lef=-inf,rig=0,ans;
+	while(lef<=rig){
+		LL mid=lef+rig>>1;
+		if(solve(n,mid).second<=m){
+			ans=mid;
+			lef=mid+1;
+		}
+		else
+		rig=mid-1;
+	}
+	enter(solve(n,ans).first+1LL*ans*m);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具