首页 > 其他分享 >题解:CF1799F Halve or Subtract

题解:CF1799F Halve or Subtract

时间:2024-09-26 10:11:50浏览次数:8  
标签:le min 题解 mR v1 mL CF1799F Subtract lambda

\(\text{Link}\)

介绍一下一种高维 wqs 的方法。

此方法来自 @YeahPotato 的专栏 严谨的 WQS 二分方法

题意

给定一个长为 \(n\) 的序列 \(v_{1\dots n}\),三个常数 \(d,a,b\)。你可以执行若干次以下两种操作:

  1. 选择 \(1\le i\le n\),令 \(v_i\gets\lceil\frac{v_i}{2}\rceil\)。
  2. 选择 \(1\le i\le n\),令 \(v_i\gets\max(v_i-d,0)\)。

你至多进行 \(a\) 次操作 1,\(b\) 次操作 2,同时对于每个元素,每种操作至多进行一次。

你需要最小化操作后 \(\sum v\) 的值并输出。

\(1\le n\le 10^5\)。

题解

两个显然的性质是,我们会把操作用完、我们会先用操作 1 再用操作 2。而根据费用流建图,答案关于操作次数 \(a,b\) 均为下凸的。

我们设操作次数限制为 \(a,b\) 时的答案为 \(f(a,b)\),那么我们需要使用两层 wqs 二分分别去除两维限制,而外层二分我们需要求出「使得 \(f(x,b)-kx\) 取到最小值的 \(x\)」,而它并不好求。问题的关键为我们无法直接通过调整斜率使得求出切到的点恰为给定值,无法同时使两维取到 \(a,b\)。

此时,我们就需要寻找求解凸函数单点值的更优方法。

有如下结论:

  • 当 \(f(x)\) 关于 \(x\) 上凸时,令 \(g_a(k)=ka+\displaystyle\max_{x}(f(x)-kx)\),那么有:\(g_a(k)\) 关于 \(k\) 下凸且 \(f(a)=\displaystyle\min_kg_a(k)\)。
  • 当 \(f(x)\) 关于 \(x\) 下凸时,令 \(g_a(k)=ka+\displaystyle\min_{x}(f(x)-kx)\),那么有:\(g_a(k)\) 关于 \(k\) 上凸且 \(f(a)=\displaystyle\max_kg_a(k)\)。

证明:不妨考虑证明其中第二条。

以下将 \(g_a(k)\) 简写为 \(g(k)\)。令 \(h(k)\) 为 \(f(x)-kx\) 取到最小值的某个 \(x\)。

证明 \(g(k)\) 上凸即证 \(\forall k_1,k_2,\forall \lambda\in[0,1]\),令 \(k=\lambda k_1+(1-\lambda )k_2\),有 \(\lambda g(k_1)+(1-\lambda)g(k_2)\le g(k)\):

\[\begin{aligned}&\lambda g(k_1)+(1-\lambda)g(k_2)\\=&\lambda [k_1a+\min_x(f(x)-k_1x)]+(1-\lambda)[k_2a+\min_x(f(x)-k_2x)]\\\le&\lambda [k_1a+(f(h(k))-k_1h(k))]+(1-\lambda)[k_2a+(f(h(k))-k_2h(k))]\\=&g(k)\end{aligned} \]

还需证明 \(g(k)\) 的最大值为 \(f(a)\),那么由于 \(f(x)\) 关于 \(x\) 下凸,必定有 \(g(f'(a))=f(a)\)。而 \(g(k)\le ka+f(a)-ka=f(a)\),所以 \(f(a)=\max_k g(k)\)。

有了这个结论,我们就把较对复杂的凸函数求值转化为了对较简单的凸函数求最值。

接下来,我们就可二分或三分求 \(g(k_1)=k_1a+\min_x(f(x,b)-k_1x)\) 的最值;而其中 \(\min_x(f(x,y)-k_1x)\) 又是关于 \(y\) 的下凸函数,再用二分或三分求 \(h(k_2)=k_2b+\min_{x,y}(f(x,y)-k_1x-k_2y)\) 的最值即可。

时间复杂度 \(O(n\log^2 v)\)。

核心代码:

const int N=5e3+10;
int n,d,a,b,v[N];
inline ll calc(int k1,int k2){
	ll s=0;
	for(int i=1;i<=n;i++)
		s+=min({v[i],(v[i]+1)/2-k1,max(v[i]-d,0)-k2,max((v[i]+1)/2-d,0)-k1-k2});
	return s;
}
inline ll solve2(int k1){
	int L=-1e9,R=0;
	while(L<R){
		int mL=L+R>>1,mR=mL+1;
		ll v1=calc(k1,mL)+1ll*mL*b,v2=calc(k1,mR)+1ll*mR*b;
		if(v1==v2) return v1;
		if(v1<v2) L=mL+1;
		else R=mR-1;
	}
	return calc(k1,L)+1ll*L*b;
}
inline ll solve1(){
	int L=-1e9,R=0;
	while(L<R){
		int mL=L+R>>1,mR=mL+1;
		ll v1=solve2(mL)+1ll*mL*a,v2=solve2(mR)+1ll*mR*a;
		if(v1==v2) return v1;
		if(v1<v2) L=mL+1;
		else R=mR-1;
	}
	return solve2(L)+1ll*L*a;
}

标签:le,min,题解,mR,v1,mL,CF1799F,Subtract,lambda
From: https://www.cnblogs.com/cyffff/p/18432918

相关文章

  • 勇攀山丘小队(翻越篇)1——题解
    前言胸有丘壑,气吞山河。正片A题:考虑使用DP,由于题目给了2个a不能在一起的限制,所以每次接上一个a都要考虑一下前面的一个状态是否也是a。于是就可以使用\(f,g\)数组,\(f_i\)表示第\(i\)个字母是a的合法情况有多少,\(g_i\)表示第\(i\)个字母是b或c的合法......
  • P8907 [USACO22DEC] Making Friends P 题解
    P8907[USACO22DEC]MakingFriendsP题解我们考虑维护每个\(i\),在\(i\)的后面有多少个点和它有朋友关系。初步的想法是每删掉一个人就给集合里所有的点连边。但是我们发现这样太不优了,有很多边会重复连很多次。优化的想法是对于\(i\),删去之后连的边就成了一个完全图,于是......
  • [GYM103119K][2020 ICPC Asia Macau] Candy Ads 题解
    题意简述有\(n\)个广告,每个广告在一个时间段内占据二维平面的矩形,\(m\)个约束表示两个广告至少有一个要被选择,选择若干广告,满足所有约束且同时刻不能有重叠的广告。Kosaraju算法流程在正图上跑一遍DFS,给每个位置打上时间戳从时间戳大到小枚举点,在反图上跑DFS,这个时候对......
  • 题解 洛谷P3398 仓鼠找 sugar
    原题链接:P3398仓鼠找sugar题解里大部分都是用的lca,然而我看不懂那些关于lca的性质是怎么证明出来的。不过这题可以直接用树链剖分来写,把模板套上去就好了。题意为查找两条路径是否存在公共点,我们只需要把其中一条路径上的点都赋值为1,然后查询另一条路径上的点的总和,如果总和......
  • [ARC062F] AtCoDeerくんとグラフ色塗り 题解
    思路对于一个点双,我们可以发现:假如它是一个简单环,那么它只能旋转这一个环,我们可以使用polya定理计算。假如它是多个环的组成,那么它的颜色可以随意调动,任何的情况都可以得到,那么假如说有\(m\)条边,方案数则为\(\binom{m+k-1}{k-1}\),我们只考虑每一种颜色的出现次数。对于......
  • 题解 QOJ5034【>.<】/ BC2401D【可爱路径】
    必可赛前公益众筹赛第一试Dhttps://qoj.ac/problem/5034,2022-2023集训队互测Round6(Nov12,2022)题目描述这原本是一道简单的最短路问题,但是由于种种地域文化,宗教信仰以及政治因素,原来一些或许可以行走的路径不能通行了。我们定义禁止路径为连续的经过一些特定的点的......
  • Luogu_P10977(AcWing_299) Cut the Sequence 题解
    解题思路考虑线性dp。首先如果存在\(a_i>m\),那肯定不满足条件,输出\(-1\)。设\(f_i\)表示前\(i\)个数分成若干段,然后每段最大数之和,其中每段内的整数之和不超过\(m\)。\(f_i\)肯定是由\(f_j\)(\(1\lej<i\))转移过来的,也就是前\(j\)个数分好后再加上\((j,i]\)这一......
  • 【OJ题解-1】稀疏矩阵乘法
    一、试题题面计算两个稀疏矩阵相乘,输出相乘的结果【输入输出约定】输入:第一行输入三个正整数p、q、r,表示p×q和q×r的两个矩阵相乘;(约定0<p,q,r≤1000)然后是第一个矩阵的输入,首先是一个整数m,表示矩阵一有m个非零元素;然后是m行,每行三个整数i,j,d,表示第i行,第j列的元素为d(约定......
  • P8906 [USACO22DEC] Breakdown P 题解
    P8906[USACO22DEC]BreakdownP题解显然的套路是删边转化为加边。考虑到维护整条路径不好维护,于是考虑转化维护\(f_{i,k},g_{i,k}\)分别表示\(1,n\)到\(i\)走了\(k\)步时的最短路。那么此时\(k\le4\)。我们先考虑\(f\)的转移,\(g\)的转移是等价的。那么对于\((......
  • 题解:CF573D Bear and Cavalry
    因为这是远古题目,所以根据现在的评测机速度,用\(O(nq)\)的做法也是可以过的。也就是说,我们可以每次操作直接修改对应位置上的数字,然后设计一种\(O(n)\)的算法求解答案。这道题类似资源分配型动态规划,所以我们可以设\(dp_i\)表示分配前\(i\)个人的答案。直接写是不行的,我......