差别

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

--- 2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/15 22:00]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/24 17:22] (当前版本)
jxm2001 [例题四]
@@ 行 209: / 行 209: @@
 === 题意 ===
+一共有 $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

用户工具

站点工具

差别

页面工具