wqs二分

wqs是用来处理一类带有恰好选 K 个这种限制的问题

我们如果发现这个答案关于k的函数是凸函数，那么就可以二分出斜率，然后拿它去切这个函数

设这个直线为\(y=ax+b\)，以上凸为例，我们要求截距最大，就是b最大，等价于\(y-ax\)最大，也就是把k限制对应的贡献-a，然后再算答案，然后就可以去除k的限制，直接求最大值，于是可以贪心或者DP，然后根据选出的k限制的贡献，判断斜率的取值

具体模型

优化一般费用流模型

考虑多次增广的费用流，每次选择最短路增广，可以发现每次选择的最短路应该只会变短，满足凸性

或者就是贪心，每次选择最优解，下一次选择肯定不会比这次优，满足凸性

DP模型

当DP中含有一位表示恰好选择k个，可以考虑只有这一维是否是凸函数，例如\(f_{i,k}\)若\(f(x)=f_{n,x}\)是凸函数，就可以wqs二分，把k这个限制优化成log，然后根据题目选择DP或贪心

例题

P5633最小度限制生成树

要求s点的度为k的MIT

证明凸性考虑最小生成树s点的度为x，然后对s点进行调整，感性理解每次修改是越来越劣，于是就是个下凸

二分一个改变量mid，给与s相连的边-mid，然后归并一下，跑kruskal，记录s的度

CF739E Gosha is hunting

有a个大师球，b个超级球，对于第i个宝可梦，用大师球有\(x_i\)的概率收回，用超级球有\(y_i\)概率收回，问期望收回多少宝可梦

发现两个求一起用的期望为\(x_i+y_i-x_iy_i\)，然后就有两种想法

费用流模型：加入A，B表示a，b限制

• s连A费用0，流量a，s连B费用0，流量b
• A连i费用\(x_i\)，流量1，B连i费用\(y_i\)，流量1
• i连t费用0，流量1，i连t费用\(-x_iy_i\)，流量为1

DP：设\(f_{i,j,k}\)表示到第i个宝可梦，用来j个大师球，k个超级球的最大期望

然后发现函数\(f(x)=f_{n,a,x}\)有凸性，于是就可以把最后一维优化成log

CF802O April Fools' Problem (hard)

有n天，每天思考一道题的时间为\(x_i\)，做一道题的时间为\(y_i\)，每天只能思考一道和做一道，要求先思考再做题，问解决k道题的最小时间

费用流模型

• s连i费用为\(x_i\)，流量为1
• i连i+1费用为0，流量为INF
• i连t'费用为\(y_i\)，流量为1
• t'连t费用为0，流量为k

然后根据凸性，二分改变量，去掉k的限制，然后考虑反悔贪心

每次把思考放进堆里，做题就考虑与堆顶能匹配，若是思考就是匹配，若是做题就是替换，然后把\(-y_i\)放进堆里

Tips

根据不多的做题经验，wqs二分处理的问题要满足凸性与求的答案最值满足一致，例如上凸对应最大值，下凸对应最小值

二分时如果开到2e9，加法时一定要*1ll