1. 从恰好选k个说起WQS二分到底在解决什么麻烦WQS二分圈内更常见的叫法是带权二分或者 Alien Trick最早被大规模讨论是因为一类恰好选取 k 个元素的最优化问题。它的核心思路极其反直觉如果一个问题的答案依赖于你选了多少个这个数量而你现在恰好被这个数量卡死了那就干脆把数量这两个字从状态里删掉换成每选一个就额外付一点钱然后通过调整这个单价把最优解重新逼回到恰好 k 个。听起来像是变魔术但它背后是一套非常干净的凸优化逻辑。先说清楚它适合谁看。如果你正在啃洛谷 P2619最小生成树恰好 k 条白边、P4383林克卡特树、P4983忘情这类题或者你在做序列分段、树上选边、资源分配时发现再多加一维就超时那这篇笔记就是写给你的。如果你连基础的动态规划都没写过建议先把背包和区间 DP 打牢因为 WQS 二分本身不难难的是它经常套在一个已经很复杂的 DP 或图论算法外面里层的那个无约束求解必须写得又快又对。我第一次接触它的时候看的是网上的模板代码二分一个数跑一遍普通的 DP 或者 MST最后用一个莫名其妙的公式减一下输出答案。代码能过但我完全不知道凭什么是它、什么时候能用、什么时候会炸。后来踩了几次坑尤其是被凸性判断错误和二分到平段直接输出错解折磨之后才慢慢捋清。这篇笔记就按我理解的顺序从问题长什么样开始一路讲到为什么这样减再到最容易翻车的几个细节尽量把那些文档里不写、但比赛里真会要命的东西说明白。1.1 一类让人血压升高的题型先看几个典型问法。给你一张图求你恰好包含 k 条白边的最小生成树给你一个序列把它切成恰好 k 段使每段代价之和最小给你一棵树删掉恰好 k 条边使剩下的连通块某种指标最优。这些题有个共同点可行性或者最优值都跟选了多少个死死绑定多一个少一个答案完全不同。如果你直接上朴素的 DP那状态里几乎必然要带一维记录当前选了几个形如dp[i][j]表示处理到第 i 个位置、已经选了 j 个的最优值。问题在于n 和 k 一旦都到 10 万级别这个 O(nk) 的状态表根本开不下、跑不动。更别提有些题里层那个转移本身还带个 log乘起来直接爆炸。所以你真正需要的是有没有一种办法能把恰好 k 个这个约束从状态维度降级成一个可调的参数答案是有的前提是答案函数长得足够规矩。1.2 维度爆炸的根源在哪我们之所以要记录选了几个是因为约束直接作用在这个数量上。但换个角度想如果真的给每个被选中的元素额外附加一个统一的代价或者奖励那就根本不需要关心选了几个了无约束地跑一遍最优解就行选多少个是算法的自然结果。这里的关键转折是——原本恰好 k 个是一个硬约束我们把它软化成了选一个就要多付 c 的代价然后用 c 这个旋钮去间接控制最终会选多少个。这个转化之所以优雅是因为它把一个离散的、卡死的约束变成了连续的、可调节的参数。而参数可以二分。这就是它和普通 DP 优化完全不同的地方别人在优化转移它在优化约束的表示方式。1.3 WQS 二分的适用门槛但它不是万能的这一点必须先泼冷水。三个硬性条件缺一不可第一你要的是恰好 k 个的最优值而不是至少或至多这类通常用不上它第二去掉个数限制后的无约束版本必须好求并且求解过程中能顺带统计出我选了几个第三也是最少被强调、最容易翻车的一条——答案关于选取个数 k 的函数必须是凸的求最小值时下凸求最大值时上凸。第三条如果没验证就硬套得到的往往是一个看起来像模像样、实际上和正确答案差十万八千里的数。后面第 5 节我会用整整一节讲怎么判断凸性、以及判断反了会发生什么。2. 核心原理把约束塞进目标函数再用切线去切凸壳很多资料一上来就甩拉格朗日乘子法把人劝退。其实你不用真的懂泛函分析只要能把几条直线画在纸上就能完全理解它在干什么。这一节我不打算堆公式而是先讲直觉再补上必要的数学形式最后讲二分的方向为什么是那样定的。2.1 把恰好 k 个改写成每个多付一点钱设 f(k) 表示恰好选 k 个时的最优值先以最小化为例。现在引入一个参数 c规定每选一个元素就要在目标函数里额外加上 c。那么对于任意一个选取方案选了 x 个它的带惩罚代价就是f(x) c·x。我们不限制个数了直接求这个带惩罚版本的最优值g(c) min over x of ( f(x) c·x )再记 k(c) 为取到这个最优值时对应的选取个数。这样恰好 k 个的约束就被吸收进了 c 里——c 越大选东西越亏算法自然就越倾向于少选c 越小甚至为负选东西越赚就会多选。c 就是一双手在背后推着 k(c) 上下移动。2.2 为什么必须要求凸性直线与下包络关键问题来了通过调节 c 得到的这些结果凭什么能还原出真正的 f(k)答案是凸性。把所有可能的选取个数 x对应的函数画出来每一条都是关于 c 的直线y x·c f(x)斜率正好是 x截距是 f(x)。而g(c)就是这一族直线的下包络取每条直线在每一点的最小值。我们要求 f(K)本质上就是想知道斜率为 K 的那条直线的截距。如果 f 是凸的那么这些直线的斜率 x 和截距 f(x) 之间的关系是凸的下包络就是一条光滑的凸折线每一个 K 都能被某条切线刚好切到或者落在一条边的两端点上。这时候在某条切线切到点 K 的那个 c 上必然有g(c) f(K) c·K移项就得到还原公式f(K) g(c) - c·K这就是所有 WQS 二分代码最后那一步减一下的来源。注意它是减去 c 乘 K不是加符号取决于你把 c 定义成惩罚还是奖励一定要跟自己的实现对齐。反过来如果 f 不是凸的那些直线画出来下包络会凹进去一块某些 K 永远不可能是某个 c 的最优解二分出来的结果根本不是 f(K)而是别的什么东西的线性组合。这就是为什么凸性检查绝对不能省。2.3 二分方向k(c) 关于 c 单调理解了包络二分的方向也就顺理成章了。因为 f 凸下包络上的最优点对应的斜率也就是选取个数会随着 c 单调变化c 增大选得越来越少。所以 k(c) 关于 c 是单调不增的求最小值、c 是惩罚的情形。既然单调就能二分。我们现在要找一个 c使得 k(c) 恰好等于目标 K。实际操作里二分框架就是猜一个 c跑无约束求解得到对应的最优值和选取个数 cnt如果 cnt 比 K 大说明选多了需要把 c 调大让它少选如果 cnt 比 K 小就调小 c。二分到最后拿某个临界 c 代进还原公式答案就出来了。下一节我会给出精确到边界处理的标准写法。3. 代码模板与还原细节从 check 函数到最终答案原理讲完到了最实在的环节。WQS 二分的代码骨架其实非常短难点全在细节边界怎么设、平段怎么处理、还原时到底减谁。我把它拆成三段来讲尽量让每段都能直接抄。3.1 一版可以直接套用的骨架以最小化、c 为惩罚为例核心代码大概长这样// check(c) 返回在每选一个额外付 c下的最优值 val以及此时选了多少个 cnt // 目标恰好 K 个 long long L -INF, R INF, bestC 0; while (L R) { long long mid (L R) 1; // 注意防溢出必要时用更宽的类型 auto res check(mid); if (res.cnt K) { // 选得还不够少说明 c 可以更大 bestC mid; // 记下可行的一个 c L mid 1; } else { R mid - 1; } } auto ans check(bestC); // 最终答案 long long result ans.val - bestC * K;这段代码的意思是我们要找使 cnt 仍然不小于 K 的最大 c。因为 cnt 关于 c 单调不增所有满足cnt K的 c 构成一个前缀左边一段满足条件的最大 c 就是答案要用的那个 c。找到它之后用val - c*K还原。这里有一个必须说清楚的点为什么是≥ K 的最大 c而不是别的因为在凸的情形下当 c 取到这个临界值时直线y K·x f(K)恰好是下包络的一部分可能和相邻的直线共线此时g(c) f(K) c·K成立还原公式才有效。如果你取的是cnt 严格等于 K 的某个 c在某些平段上可能根本不存在或者对应的结果不稳定。用≥ K 的边界更稳。3.2 还原公式的符号一定要跟自己的约定对齐我见过太多人代码逻辑全对最后答案差了2*c*K这种量级根源全是符号。这里给一个永远不会错的自检方法拿一个你能手算的极小样例比如 K0看看还原出来的值是不是就等于一个都不选的答案再拿 K1手动跑一次 check检查val - c*K是不是等于真实最优值。两个点都对上符号就没问题。再强调一次约定如果你把 c 定义成每选一个扣 c奖励那 check 里的最优值 g(c) 实际是min(f(x) - c·x)还原时要写成g(c) c*K。惩罚和奖励两种写法只差一个整体符号但代码里混用就会出错。我的习惯是统一用惩罚选一个加 c因为二分方向c 越大选越少更符合直觉。3.3 二分边界怎么定才不会被精度和溢出坑边界的取值不是随便拍脑袋。c 的物理意义是边际代价或者斜率所以它的大致范围可以从题目里数值的量级推出来。比如 Tree I 里边权最大是 100那么把 c 设在[-100, 100]就足够了因为超过这个范围不可能再让某条边值不值的判断发生变化。一般经验是c 的绝对值上界取到单个元素权值的最大可能变化量就够多开一点无所谓但别开到1e18二分次数会变多而且中间计算容易溢出。另外要注意二分次数的收敛性。整数二分的循环条件是L R天然会在 log(range) 次内结束不需要额外设精度。但如果题目里 c 是实数斜率本身是有理数、需要二分浮点那就得用固定迭代次数通常 60 次左右足够双精度收敛或者 100 次更保险。浮点版本最容易踩的坑是两个数看起来相等其实差了 1e-12导致 cnt 在一个 c 附近来回跳最后还原出一堆小数误差。这种题要么全程用整数把斜率放大成整数来二分要么最后对答案做一次取整。4. 实战Tree I 恰好 k 条白边的最小生成树光讲原理不过瘾拿最经典的 Tree I 走一遍完整流程。这道题的输入、转换、check、还原几乎能覆盖 WQS 二分的所有核心操作把它吃透其他题都是换皮。4.1 题意与它为什么是凸的题目大意给一张 n 个点、m 条边的图每条边有黑白两种颜色之一和一个权值。要求找一棵恰好包含 k 条白边的最小生成树输出它的总权值。这里恰好 k 条白边就是那个卡人的约束f(k) 就等于恰好 k 条白边的最小生成树权值。为什么 f 是凸的直觉解释是为了让白边变多你被迫用越来越贵的方式去替换黑边边际成本越来越高所以 f 的差分单调不降也就是下凸。严格证明可以借助拟阵的性质但比赛里通常是凭这种越换越贵的直觉来判定加上对拍验证。这也提醒一句凸性判断不要凭玄学能对拍就一定要对拍一个小范围的所有 k。4.2 check 函数怎么写白边加惩罚后跑 MSTcheck(c) 的做法是把每一条白边的权值统一加上 c然后正常跑最小生成树同时统计用到的白边条数 cnt。返回 (MST总权值, cnt)。代码如下struct Edge { int u, v, w; bool white; }; int n, m, k; vectorEdge edges; int fa[50005]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } // 返回 {MST权值和(含惩罚), 白边条数} pairlong long,int check(long long c) { for (int i 1; i n; i) fa[i] i; // 关键白边权值加 c排序时同权值让黑边优先 sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { long long wa a.w (a.white ? c : 0); long long wb b.w (b.white ? c : 0); if (wa ! wb) return wa wb; return a.white b.white; // 相等时黑边(false)排前面 }); long long tot 0; int cnt 0; for (auto e : edges) { int u find(e.u), v find(e.v); if (u v) continue; fa[u] v; tot e.w (e.white ? c : 0); if (e.white) cnt; } return {tot, cnt}; }这里有一个特别关键的细节当白边加惩罚后和黑边权值相等时排序要让黑边优先。为什么因为我们要让 cnt 关于 c 单调不增。如果相等时白边随便排前面那么同一个 c 可能因为排序不稳定而给出不同的白边数量二分的单调性就被破坏了。让黑边优先等价于在等权时尽量少用白边这样 cnt 作为 c 的函数是单调不增的二分的收敛性才有保障。这个坑我在第一次写的时候完全没意识到对拍小数据才发现 cnt 会跳。4.3 二分与答案输出二分框架直接用第 3 节的骨架把 K 换成题目给的 kcheck 换成上面这个。二分范围[-100, 100]就足够边权最大 100。最后auto res check(bestC); cout res.first - bestC * k endl;我用一组小数据验算过n3k1白边权值分别在某些值上时手算的答案和程序输出完全一致。这里再补一个个人心得——如果你不确定凸性或者不确定符号最省事的办法是把 k 从 0 到 n 全部暴力跑一遍真实 DP小数据下可以画出 f(k) 的图像肉眼确认它下凸再拿这组数据去对拍 WQS 的结果。这招虽然土但救我至少两次尤其是在树上那种肉眼完全看不出来的题目上。5. 常见理解误区逐条拆这些坑我基本都踩过WQS 二分的代码短但理解偏差极多。很多人能对着模板改出来过题一换题型就全乱。这一节把最容易出问题的几个认知误区挑出来每条都给出正确认识配合表格方便对照记忆。误区描述正确认识所有恰好 k 个的题都能用 WQS必须验证答案关于 k 凸否则得到的是错误值凸性方向随便算出答案就行求最小要下凸求最大要上凸方向反了结果系统性偏差二分到 cnt 恰好等于 K 就行平段上可能取不到恰好相等要用≥ K 的边界处理惩罚加在白边权值上还是加在总答案上没区别必须加在每次选取上加在总答案上无法影响选取决策实数二分随便设个 eps 就够了平段附近 cnt 会抖建议整数化或加大迭代次数5.1 误区一把能过样例当成凸性成立最常见的翻车方式是题目的答案函数其实不凸但因为样例刚好在凸的那一段代码轻松过样例一交就 WA。记住WQS 二分求出的g(c) - c*K在 f 不凸的时候等于的是f 的下凸包在 K 处的取值而不是 f(K)。两者之间差多少完全取决于 f 凹下去多深。判断凸性的实用做法小数据下暴力求出所有 f(k)检查相邻差分f(k1)-f(k)是否单调不降。单调就放心用不单调就赶紧换思路。5.2 误区二凸性方向判断反了求最大值的题f 应该是上凸的差分单调不增。很多人不管三七二十一照抄最小化的模板结果二分方向反了、还原符号也反了答案看着像对的其实是错的。我建议统一处理如果原题求最大值把所有值取负转成求最小值来做最后答案再取负回来。这样模板永远只用一套脑子不用跟着切来切去出错概率大幅下降。5.3 误区三平段处理不当cnt 不单调当 f 的相邻差分出现相等也就是斜率有重复时下包络上会有一段平的区域。此时同一个 c 可能对应多个最优的选取个数cnt 不是唯一确定的。这就是为什么第 4 节的代码要在排序时规定优先选谁——我们要人为地固定一个规则让 cnt 在 c 变化时保持单调这样二分才有意义。更严谨的做法是让 check 同时返回最小可能的 cnt 和最大可能的 cnt判断 K 是否落在这个区间内落在里面就说明这个 c 是合法的切点。对绝大多数题目只要排序规则定死简单版的≥ K 边界就够用了。5.4 误区四惩罚加错位置惩罚必须加在每一次选取上也就是影响内层算法的决策。有人偷懒在算完无约束最优之后才加一个c*K这是完全无效的——因为此时选取个数根本没被 c 影响cnt 还是原来的数二分没有意义。判断标准很简单改变 ccnt 必须真的跟着变如果 cnt 纹丝不动那你的惩罚就是加错了地方。5.5 误区五实数二分的精度陷阱有些题的斜率本身是有理数c 需要二分实数。这时常见的坑是 eps 设太大导致没收敛到临界点或者太小导致死循环、精度丢失。我的经验是固定迭代 60 到 100 次不要用 while 加 eps 判断并且在最后还原答案时注意把结果 round 到最近的整数。如果题目允许更好的办法是把所有权值放大整数倍把 c 也变成整数来二分彻底避开浮点。6. 进阶玩法与调试经验WQS 是怎么套进复杂 DP 的掌握了 Tree I你会发现 WQS 二分本身只是外层的壳真正的难度在于内层那个无约束求解能不能写对、写快。这一节聊聊它在树形 DP 和序列 DP 里的常见组合以及我自己总结的一套调试流程。6.1 林克卡特树树上 DP 套 WQS林克卡特树是 WQS 二分 树形背包的经典组合。题意大致是从树上删掉恰好 k 条边使剩余的若干连通块直径之和最大或类似目标。内层的无约束求解是一个树形 DP状态里不需要记录删了几条边只需按每个点合并子树的贡献来转移外层用 WQS 给删一条边附加一个代价 c二分它使删除边数逼近 k。这类题的坑在于内层 DP 本身状态设计就比较绕再加上 WQS 外层的符号调试难度翻倍。写这类题我一般分两步走先把 c 固定成一个具体值单独测试内层 DP 的正确性和暴力对拍无约束版本确认内层没问题后再接上二分。千万不要一上来就二分 DP 一起调你根本分不清是内层写错了还是外层符号错了。6.2 调试清单按这个顺序查能省一半时间踩了无数次坑之后我整理出一套排查顺序遇到 WA 或者 RE 就照这个表格从前往后过一遍检查项常见症状排查方法凸性是否成立样例过、对拍挂小数据暴力求 f(k)检查差分单调二分方向cnt 越二分越远打印每轮 mid 和 cnt看趋势排序/选择规则的平段处理cnt 在小范围内抖动固定同权优先规则让 cnt 单调还原符号答案整体差一个常数倍用 K0、K1 手算对照二分上下界找不到临界 c答案偏大偏小根据元素权值量级重设范围溢出中间结果为负、异常大惩罚累加用 long long6.3 几个反直觉的小结论最后分享几个我实际做题中才领悟的点。第一WQS 二分不要求 f 是严格的凸允许有平段甚至有多个相等的差分只要整体不下凹保持凸性就行。第二二分出来的 c 不一定是最优解恰好选 K 个的那个 c很多时候是一个临界值实际最优方案选的数量是 K 或者 K 附近还原公式依然成立这就是凸性的威力。第三如果一道题你发现怎么调 WQS 都不对但暴力 DP 是对的先别怀疑模板八成是凸性不满足赶紧回去重新审视题目。第四多做题比多背模板有用得多——WQS 的模板总共不到二十行真正难的是识别哪些题可以用、以及怎么写内层。我个人在实际操作中的体会是WQS 二分最考验的不是编码能力而是敢不敢在写之前先花五分钟确认凸性。我早期最大的教训就是看到恰好 k 个就直接上模板结果在一道看似很套路的题上卡了两个小时最后发现答案函数根本不凸白白浪费了整场时间。现在的习惯是不管多熟练遇到新题第一步永远是拿小数据暴力跑出 f(k) 序列画个图或者看看差分确认凸性之后再动键盘写二分。这一步花不了几分钟但能帮你避开绝大多数看起来对、实际全错的坑。如果你也在学这部分不妨把这个习惯加进你的解题流程里比记住任何模板都值钱。