文章目錄

• 應(yīng)用分析
• 算法分析
• WQS二分精髓的兩點(diǎn)細(xì)節(jié)（博客重點(diǎn)！）
• 真題分析
• • [國家集訓(xùn)隊(duì)]Tree Ⅰ
  • 忘情
  • 星際廣播

網(wǎng)上很多博客寫得模模糊糊的，對(duì)我這個(gè)新手可是一點(diǎn)都不友好。
昨天一天都在研究這個(gè)東西，分享一下自己的拙見。
百度搜“WQS二分”的第一篇，搜“WQS的一個(gè)細(xì)節(jié)及證明”的第一篇質(zhì)量還是可以的，用來大致理解和細(xì)節(jié)理解，本文前部分借鑒了上述兩篇博客。
我這個(gè)就是實(shí)戰(zhàn)理解吧。。。

應(yīng)用分析

$\text{WQS}$ 二分通常用來解決下面這類問題：

給定若干 $n$ 個(gè)物品，要求從中恰好選 $m$ 次，最大化 / 最小化 選的物品權(quán)值和。

---

使用條件：

• 設(shè) $g(i)$ 選 $i$ 個(gè)物品的最優(yōu)答案，將所有 $(i,g(i))$ 的點(diǎn)畫出來，必須組成一個(gè) 凸包 （上凸包、下凸包均可）。

因?yàn)槭峭拱?#xff0c;對(duì)應(yīng)性質(zhì)為斜率 遞增 / 遞減。

---

這種題目往往有下列特點(diǎn)：

• 如果不限制選的個(gè)數(shù)，那么很容易求出最優(yōu)方案。（所以一般用來優(yōu)化 $dp$）
• 選的物品越多，權(quán)值越 大 / 小。

---

判斷能否使用的方法：

• 打表看 $(i,g(i))$ 擬合出的圖形是凸包。
• 滿足兩個(gè)特點(diǎn)。

常用第二種方法，感性理解。感覺可以用 $\text{WQS}$ 二分，那就大膽用 $\text{WQS}$ 二分。

---

綜上。

判斷能否使用 $\text{WQS}$ 二分的流程：

題目能轉(zhuǎn)化成： 一共有 $n$ 個(gè)數(shù)，要求剛好選 $m$ 次，有某種限制，以某種方式計(jì)算每次選的物品的某個(gè)屬性和，選多少次以及怎么選都會(huì)影響到答案。

然后能設(shè) $dp(i,j):$ 到 $i$ 為止，選了 $j$ 次的最優(yōu)答案。

然后有轉(zhuǎn)移：$dp(i,j)=\max /\min (dp(k,j?1)+cost(k,i))$ 類似的。

復(fù)雜度不管怎么優(yōu)化都至少是 $O(nm)$ 及以上的。

無法接受。

打表發(fā)現(xiàn)形成凸包 、斜率單調(diào) / 滿足特點(diǎn)。

且如果這題沒有恰好選 $m$ 個(gè)的限制就可以 $dp$ 降維轉(zhuǎn)移。

就可以用 $\text{WQS}$ 二分降維。

時(shí)間復(fù)雜度 $O(n\log V)$。

---

算法分析

Part 0：前提假設(shè)。

算法分析均假設(shè)題目要求是最大化權(quán)值。

算法分析均假設(shè) $(i,g(i))$ 擬合出的圖形是上凸包。

---

Part 1：二分的部分。

先不考慮 $m$ 的限制。

二分一個(gè) $mid$，表示選一次物品的附加權(quán)值。

• 注意：是『選一次』，不是『選一個(gè)』。因?yàn)橛械念}目選一次對(duì)應(yīng)一段區(qū)間，即多個(gè)物品。

則選的次數(shù)越多，權(quán)值越大。

所以當(dāng)最優(yōu)方案選的物品次數(shù)大于 $m$ 時(shí)，就減小 $mid$，否則增加 $mid$。

最后答案去掉 $mid$ 的影響即可。

---

part 2：二分 $\text{check}$ 的部分。

• Ⅰ

我們先看一下 $(i,g(i))$ 構(gòu)成的凸包樣子。

二維平面坐標(biāo)系中，橫坐標(biāo) $x$ 軸表示：選 $x$ 次物品；縱坐標(biāo) $y$ 軸表示：選 $x$ 次情況下的最大答案。

顯然只要求出 $x=m$ 對(duì)應(yīng)凸包上的點(diǎn)即可，即 $g(m)$。

但問題就是不能很快速地求出 $g(m)$ 。

也就是說 這個(gè)凸包暫時(shí)是求不出來的，但是可以知道這個(gè)凸包的形狀——上凸包。

于是考慮 用直線去切凸包 。

顯然可以得到一個(gè)最大值（最先切到的點(diǎn)就是最優(yōu)答案選物品的次數(shù)以及最大答案）

同時(shí)，也顯然這個(gè)最大值點(diǎn)不一定全都是恰好在 $x=m$ 處的。

e.g. 假設(shè) $m=12$，隨便用一條斜率為 $k$ 的直線去切，紅色直線就切在了 $x=6,x=9$ 的點(diǎn)。

上面說到，斜率為 $k$ 的直線切凸包，每次最先切到的點(diǎn)就是最優(yōu)答案。

所以我們可以通過 調(diào)整斜率 $k$ 來使得直線切到不同的位置點(diǎn)。

由于 $g(x)$ 的斜率單調(diào)，所以直線斜率 $k$ 切到的點(diǎn)同樣具有單調(diào)性。

e.g. 如圖，斜率越小，切到凸包的點(diǎn)越往右，即越大。

• Ⅱ

假設(shè)一個(gè)斜率為 $k$ 的直線，考慮如何求得該直線最先切在凸包的位置，即 $(x,g(x))$。

發(fā)現(xiàn)，斜率為 $k$ 的直線在凸包上切到的所有點(diǎn)，可以和 $k$ 一起唯一地刻畫一條完整直線 $y=kx+b$ 。

且最先切的點(diǎn)，即要求的位置，和 $k$ 刻畫的直線的截距 $b$ 一定是最大的。如圖。

根據(jù)小學(xué)初中知識(shí)，截距 $b=y?kx$。具體地，截距 $b(x)=g(x)?k?x$。

觀察這個(gè)式子，發(fā)現(xiàn)式子等價(jià)于：只要把每次選擇獲得的權(quán)值和 $?=k$，然后正常求 在選任意次物品情況下最大的答案是多少 即可。

這個(gè)最大答案就是最大的截距。

而這種問題用 $dp$ 是線性 $O(n)$ 可做的。

并且 $dp$ 的同時(shí)可以知道最大值點(diǎn)在凸包的位置，那么我們就知道了 $(x,g(x))$。

這樣就可以返回然后判斷二分了。

• Ⅲ

綜上需要明確的是$\text{WQS}$ 二分模板代碼中：

二分的是切凸包的直線斜率 $k$。調(diào)整斜率就是調(diào)整二分的額外貢獻(xiàn)。即附加貢獻(xiàn)就是斜率。

二分的檢查函數(shù)（帶額外權(quán)值的）中的 $dp$ 算的是直線的截距。

---

WQS二分精髓的兩點(diǎn)細(xì)節(jié)（博客重點(diǎn)！）

建議先做個(gè)模板題，再做個(gè)加強(qiáng)題，最好加強(qiáng)題半對(duì)半錯(cuò)，然后暈乎乎地過來哈哈哈

如果你有把最后二分出的斜率對(duì)應(yīng)的檢查函數(shù)中的最大值點(diǎn)輸出出來看過，發(fā)現(xiàn)貌似這個(gè)最大值點(diǎn)也不等于 $m$ 。

如果你發(fā)現(xiàn)自己最后二分出的斜率 $\pm 1$ 可能就會(huì)過掉這個(gè)題，或者過的點(diǎn)更多。

如果你覺得最后的答案不應(yīng)該用 $m$ 乘以附加權(quán)值再被去掉。而應(yīng)該用附加權(quán)值對(duì)應(yīng)的最大值點(diǎn)來乘。

等等等等$\dots$。

那么證明你已經(jīng)走到了 $\text{WQS}$ 的精髓部分了。

那就是初學(xué)者都要疑惑的兩點(diǎn) ：

• 你覺得最后的答案不應(yīng)該用 $m$ 乘以附加權(quán)值再被去掉。而應(yīng)該用最優(yōu)方案實(shí)際選的次數(shù)來乘。

  這個(gè)問題如果你有，證明你沒有搞明白二分的究竟是什么，檢查函數(shù) $dp$ 算的又究竟是什么。

  再聲明一下，二分的是斜率，檢查函數(shù)算的是該斜率對(duì)應(yīng)的最優(yōu)方案的截距。

  仔細(xì)觀察，這張圖暗藏玄機(jī)！

  你有沒有發(fā)現(xiàn)這條直線切了 $x=3,4,5,6$ 的點(diǎn)！（最先切到的可能同時(shí)是一段點(diǎn)）

  這也是為什么 $mid$ 時(shí)最優(yōu)點(diǎn) $<m$ ；$mid+1$ 時(shí)最優(yōu)點(diǎn) $>m$。

  也即是前面說的，斜率在一定范圍內(nèi)都是切的一個(gè)點(diǎn)。

  我們現(xiàn)在的最佳直線就是這條紅線，而我們記錄的凸包上的點(diǎn)也許是 $x=3,x=6$，而最后 $m=4/5$。

  但是這些點(diǎn)都是在直線上的，而我們用 $dp$ 出來的最大截距 $b$ 要 $+k?m$ 才能 $=g(m)$。

  所以的確是要去掉 $m?$ 最后二分定的斜率。

• 假設(shè)最后斜率為 $mid$ 最大值點(diǎn) $<m$ ；而斜率為 $mid+1$ 最大值點(diǎn)又 $>m$。也就是說，似乎必須要附加權(quán)值為小數(shù)，才能求出 $x=m$ 的情況。

  但你如果寫小數(shù)二分，那就會(huì)遇上 $\text{TLE}$ 的結(jié)果。

  事實(shí)上，是可以不用二分到小數(shù)的。

  我們?cè)谂判蛏献鳇c(diǎn)手腳，使得當(dāng)選的次數(shù) $\ge m$ 是更新答案。（符號(hào) $\ge,\le $ 看對(duì)應(yīng)排序和二分寫法）

  理論的分析就是上面那張圖。由于 $x$ 是一個(gè)整數(shù)，切出來的直線的斜率 $k$ 在一個(gè)范圍 $[k_l,k_r]$ 內(nèi)都是落在同一個(gè) $x$ 點(diǎn)上。

  注意每個(gè)屬性都要定義偏序關(guān)系

  根據(jù)題目是求最大值還是最小值，來定二分的邊界是在負(fù)數(shù)還是在正數(shù)還是都有。

  還有自己是寫的額外加貢獻(xiàn)還是額外減貢獻(xiàn)，最后去掉答案的時(shí)候要對(duì)應(yīng)。

  一定要搞清楚自己二分造成的影響是會(huì)使得選的次數(shù)增多還是減小。

  這些都是每個(gè)人不同的代碼習(xí)慣造成的差異。

  e.g 求分若干組的最大值，假設(shè)二分是在負(fù)數(shù)內(nèi)l=-1e6,r=0，并且寫得是減法，也即是分的組數(shù)越多獲得的額外貢獻(xiàn)越大。所以當(dāng)最優(yōu)答案 $\ge$ 限制時(shí)更新，并且減少增加的額外貢獻(xiàn)，對(duì)應(yīng) r=mid-1。

  e.g. 求分若干組的最大值，假設(shè)二分時(shí)在正數(shù)內(nèi) l=0,r=1e6，并且寫的減法，也即是分的組數(shù)越多獲得的額外貢獻(xiàn)越小（是負(fù)的），所以當(dāng)最優(yōu)答案 $\le$ 限制時(shí)更新（減多了，才會(huì)使得分的段數(shù)變少），并且增加獲得的額外貢獻(xiàn)，對(duì)應(yīng) r=mid-1。

  但實(shí)際上 $\le ,\ge$ 要看第二屬性的排序。

  最后我們強(qiáng)調(diào)一下為什么要“每個(gè)屬性都定義偏序關(guān)系”！

  首先你要知道凸包上的所有點(diǎn)并不是都存了下來的，比如上面圖的凸包就是只存在藍(lán)點(diǎn)。

  為什么只存在藍(lán)點(diǎn)，是因?yàn)槲覀兊牡诙傩云蚴沟卯?dāng)直線截距相同時(shí)我們只存儲(chǔ)最小值 / 最大值（最左邊點(diǎn)/最右邊點(diǎn)）

  而你的 $x=m$ 答案點(diǎn)就在相同截距最左邊點(diǎn)的右邊，最右邊點(diǎn)的左邊。

  如果不寫當(dāng)?shù)谝粚傩韵嗤瑫r(shí)，第二屬性怎么排，你的凸包可能刻畫出來就是有問題的。

  這里說第一屬性，第二屬性可能你壓根不理解。具體可見下面三道真題分析。

真題分析

[國家集訓(xùn)隊(duì)]Tree Ⅰ

[國家集訓(xùn)隊(duì)]Tree I

對(duì)全部邊進(jìn)行排序，跑最小生成樹，我們可以得到最優(yōu)的答案，但是白邊不一定恰好是要求的條數(shù)。

二分白邊的額外權(quán)值。再跑最小生成樹。

如果白邊少了，說明白邊整體權(quán)值比較大，所以沒被選中。那我就對(duì)白邊都減少額外權(quán)，這樣的話，被選中的白邊會(huì)增多。

同理，如果被選白邊數(shù)量多了，我就給白邊們都多加一點(diǎn)額外權(quán)。

這里當(dāng)白邊邊權(quán)和黑邊邊權(quán)相同時(shí)，我們必須欽定先選白邊還是先選黑邊。

如果我們排序是先選白邊，那么求得就是在二分的斜率切到的所有點(diǎn)中最靠右的點(diǎn)，二分寫法得用 $\ge$ 判斷更新；

反之，邊權(quán)相同時(shí)先選黑邊，那么求得的就是切到的所有點(diǎn)中最靠左的點(diǎn)（最小點(diǎn)），二分寫法得用 $\le$ 更新判斷。

因?yàn)樽钭筮咟c(diǎn) $\le m\le$ 最右邊點(diǎn)。

這里的兩個(gè)屬性分別是邊權(quán)（第一屬性）和顏色（第二屬性） 。

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100005 struct node { int u, v, w, c; }E[maxn]; int u[maxn], v[maxn], w[maxn], c[maxn], f[maxn]; int cnt, ans, n, m, k; int find( int x ) { return f[x] == x ? x : f[x] = find( f[x] ); } void check( int x ) {cnt = ans = 0;for( int i = 1;i <= m;i ++ )if( c[i] ) E[i] = (node){ u[i], v[i], w[i], c[i] };else E[i] = (node){ u[i], v[i], w[i] - x, c[i] };sort( E + 1, E + m + 1, []( node x, node y ) { return x.w == y.w ? x.c < y.c : x.w < y.w; } );iota( f + 0, f + n, 0 );for( int i = 1;i <= m;i ++ ) {int fu = find( E[i].u ), fv = find( E[i].v );if( fu == fv ) continue;f[fv] = fu;cnt += (E[i].c ^ 1);ans += E[i].w;} } signed main() {scanf( "%lld %lld %lld", &n, &m, &k );for( int i = 1;i <= m;i ++ )scanf( "%lld %lld %lld %lld", &u[i], &v[i], &w[i], &c[i] );int l = -100, r = 100, ret;while( l <= r ) {int mid = l + r >> 1;check( mid );if( cnt >= k ) ret = mid, r = mid - 1;else l = mid + 1;}check( ret );printf( "%lld\n", ans + ret * k );return 0; }

忘情

luogu-P4983 忘情

先化式子：
$$\frac{(({\sum }_{i=1}^n{x}_i\times \bar{x})+\bar{x}{)}^2}{{\bar{x}}^2}=\frac{{\bar{x}}^2({\sum }_{i=1}^n{x}_i{)}^2+2{\bar{x}}^2{\sum }_{i=1}^n{x}_i+{\bar{x}}^2}{{\bar{x}}^2}=(\sum _{i=1}^n{x}_i{)}^2+2(\sum _{i=1}^n{x}_i)+1=(\sum _{i=1}^n{x}_i+1{)}^2$$
設(shè) $f(i,j):$ 前 $i$ 個(gè)數(shù)分成 $j$ 段的最小值。

$f(i,j)=\min \{f(k,j?1)+(sum[i]?sum[k]+1{)}^2\}$。

直接 $\text{WQS}$ 二分：每分一次段就 $+x$。

那么 $dp$ 就變成一維了，斜率優(yōu)化部分就不再多說了。

這里是段分的越多，獲得的額外價(jià)值就越多。

而我想要的是最小值。

注意斜率優(yōu)化里面的彈隊(duì)列的寫法，$=$ 問題我也彈出了，也就是說第一屬性相同時(shí)我選擇了第二屬性較大的。

這里第二屬性就是到 $i$ 位置分的段數(shù)，即最后斜率切的最右邊的點(diǎn)。

那么限制 $m$ 應(yīng)該在這個(gè)點(diǎn)的左邊，所以寫法是 $g[n]\ge m$ 才更新。

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100005 int n, m; int x[maxn], f[maxn], g[maxn], q[maxn], sum[maxn];double slope( int x, int y ) {return ( (f[x] - (sum[x] << 1) + sum[x] * sum[x]) - (f[y] - (sum[y] << 1) + sum[y] * sum[y]) ) * 1.0 / (sum[x] - sum[y]); }void check( int x ) {int head = 1, tail = 0; q[++ tail] = 0;for( int i = 1;i <= n;i ++ ) {while( head < tail and slope( q[head], q[head + 1] ) <= (sum[i] << 1) ) head ++;f[i] = f[q[head]] + (sum[i] - sum[q[head]] + 1) * (sum[i] - sum[q[head]] + 1) + x;g[i] = g[q[head]] + 1;while( head < tail and slope( q[tail - 1], q[tail] ) >= slope( q[tail], i ) ) tail --;q[++ tail] = i;} }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &x[i] );for( int i = 1;i <= n;i ++ ) sum[i] = sum[i - 1] + x[i];int l = 0, r = 1e16, ans;while( l <= r ) {int mid = ( l + r ) >> 1;check( mid );if( g[n] >= m ) ans = mid, l = mid + 1;else r = mid - 1;}check( ans );printf( "%lld\n", f[n] - ans * m );return 0; }

星際廣播

給定一個(gè)長為 $n$ 的字符串 $s$，第 $i$ 個(gè)星球的編號(hào) $s_i$ 只可能為 $R/B/Y$。

現(xiàn)在可以給長度為 $l$ 的區(qū)間進(jìn)行星際廣播，使得區(qū)間內(nèi)的所有廣播站編號(hào)全部變?yōu)橹付ň幪?hào)。

限制最多只能進(jìn)行 $m$ 次廣播。

剩下的想改變的廣播站只能單獨(dú)進(jìn)行電話連線發(fā)出改變成指定編號(hào)的指令。

求最少需要和多少個(gè)星球單獨(dú)電話才能使得 $n$ 個(gè)星球的編號(hào)統(tǒng)一。

solution

顯然這個(gè)最多可以變成恰好，因?yàn)閺V播不帶來代價(jià)，我們肯定是能用則用。

所以開始現(xiàn)特判當(dāng) $m?l\ge n$ 時(shí)，輸出 $0$。

我們直接枚舉最后統(tǒng)一的編號(hào)是哪種。假設(shè)為 $ch$，然后對(duì)每一種都進(jìn)行下列算法。

現(xiàn)在 $m?l<n$，貪心的策略告訴我們存在一種最優(yōu)方案使得廣播的區(qū)間一定是不交的。

我們肯定是用廣播盡可能地覆蓋不同編號(hào)的星球。

如果列出暴力 $dp$ 及轉(zhuǎn)移方程，可以發(fā)現(xiàn)能 $\text{WQS}$ 降維。這里不再重復(fù)。

直接二分斜率（每廣播一次帶來的額外代價(jià)）。

設(shè) $f(i):$ 到 $i$ 為止被改變編號(hào)的星球個(gè)數(shù)。

設(shè) $g(i):$ 到 $i$ 為止最少使用的廣播次數(shù)。

記 $c(i)={\sum }_{j=1}^i[s_j=ch]$。

則有轉(zhuǎn)移 $f(i)={\max }_{1\le j\le i?l}\{f(j)+c(i)?c(i?l)\}$。

即被改變的星球個(gè)數(shù)是第一屬性，使用的廣播次數(shù)是第二屬性。

這里我指定最小廣播次數(shù)優(yōu)，所以求得的是凸包相同斜率的最左邊點(diǎn)，所以二分要用 $\le m$ 判斷。

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 1000005 int n, m, l; char s[maxn]; int f[maxn], g[maxn], c[maxn], q[maxn]; int check( int x ) {int pos = 0;for( int i = 1;i <= n;i ++ ) {if( l < i ) {if( f[pos] < f[i - l] or (f[pos] == f[i - l] && g[pos] >= g[i - l] ) ) pos = i - l;f[i] = f[pos] + c[i] - c[i - l] + x;g[i] = g[pos] + 1;}else f[i] = c[i] + x, g[i] = 1;}pos = 0;for( int i = 1;i <= n;i ++ )if( f[i] > f[pos] or (f[i] == f[pos] and g[pos] < g[i] ) ) pos = i;return pos; } int solve( char x ) {for( int i = 1;i <= n;i ++ ) c[i] = c[i - 1] + (s[i] != x);int l = -1e6, r = 0, ans;while( l <= r ) {int mid = l + r >> 1;int pos = check( mid );if( g[pos] <= m ) ans = mid, l = mid + 1;else r = mid - 1;}int pos = check( ans );return c[n] - (f[pos] - m * ans); } signed main() {scanf( "%lld %lld %lld %s", &n, &m, &l, s + 1 );if( m * l >= n ) return ! puts("0");int ans1 = solve( 'R' );int ans2 = solve( 'B' );int ans3 = solve( 'Y' );printf( "%lld\n", min( ans1, min( ans2, ans3 ) ) );return 0; }

總結(jié)

以上是生活随笔為你收集整理的【学习笔记】WQS二分详解及常见理解误区解释的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。