带权二分

· · 题解

前面的话

这篇博客大概是带权二分(wqs 二分，是叫这个名字吧？)的入门博客，希望大家点个赞?。

引入

给你一个序列 a_1,a_2,a_3..a_n 。其中 a_i\in \mathbb{Z^*} 。可以把序列分为 k 段。定义每一段的价值为 (\sum_{i= 1}^n a_i)^2 ，现在要求 k 的总和最小。形式的，我们要最小化 ans=\sum_{i=1}^{k}(\sum_{a_j\in U_i} a_j) ^ 2 。

分析

总结

例题

很遗憾，我并没有找到太多的例题，但大概也有非常好的训练效果。

P4983 忘情

题意

也是分 m 段，每一段的价值为 (1+\sum_{i=1}^n a_i)^2 最小化价值和。

分析

同上题。式子基本一模一样。那么省去二分斜率这些步骤。我们重点分析一下 dp(i)=\min\{dp(j) + (S_i - S_j + 1) ^ 2 + val\} 这个式子。令 j 为 i 的转移点。那么 dp(i)=dp(j)+S(i)^2 + S(j)^2 + 1 + 2S(i) - 2S(j) - 2S(i)S(j) + val 移项之后 dp(i)-S(i)^2-1-val-2S(i)= -2S(i)S(j) + dp(j)+S(j)^2 - 2S(j) 。由于我们要维护 dp(i) 的最小值，所以我们考虑用单调栈维护一个凸壳。然后就是斜率优化的模板了 y = -bx + k，其中 2S(i) 为 x ，斜率为 b = S(j) ，k = dp(j)+S(j)^2-2S(j) 。那么一次 dp 的复杂度就下降到 O(n) 了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
} 
#define ll long long
const ll inf = 1e18;
const int N = 1e5 + 100;
ll f[N],g[N],q[N],s[N];
int n,m;
#define Y(a) (f[a]+s[a]*s[a]-2*s[a])
#define X(a) (s[a]) 
long double K(int a,int b) {
    return (long double)(Y(b) - Y(a)) / (X(b) - X(a));
}
void check(ll mid) {
    memset(f,0x3f,sizeof(f));memset(g,0,sizeof(g));
    f[0] = 0;int l = 1,r = 1;
    q[1] = 0;
    for(int i = 1;i <= n;i++) {
        while(l < r && K(q[l],q[l + 1]) < 2 * s[i]) l++;
        f[i] = f[q[l]] + (s[i] - s[q[l]] + 1) * (s[i] - s[q[l]] + 1) + mid;
        g[i] = g[q[l]] + 1;
        while(l < r && K(q[r - 1],q[r]) > K(q[r - 1],i)) r--;
        q[++r] = i;
    }
}
int main() {
    n = read();m = read();
    for(int i = 1;i <= n;i++) s[i] = s[i - 1] + read();
    ll l = 0,r = inf,ans = 0;
    while(l <= r) {
        ll mid = l + r >> 1;check(mid);
//      cout << g[n] << endl;
        if(g[n] <= m) ans = mid , r = mid - 1;
        else l = mid + 1;   
    }
    check(ans);
    printf("%lld\n",f[n] - m * ans);
    return 0;
}

[国家集训队2]Tree I

分析

我们令 f(x) 为选择 x 条白边的最小生成树的代价。根据直觉的分析，在某一个位置 pos 前时，我们选择白边比黑边要优，是一个逐渐增加，斜率逐渐减小的函数。而 pos 后面选择黑边要优，是一个斜率的增加，值不断减小的函数。那么我们给白色的边加上一个权值 val ，在这个情况下做最小生成树。最后返回使用的白色边的个数和最小生成树的代价。那么二分完 val 之后，最后的答案为 Ans_{Mst} - k \times val 。总的复杂度为 O(n\log n\log w) 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 1000;
struct Edge {ll x,y,w,col;}e[N];
int read() {int x;scanf("%d",&x);return x;}
ll n,m,k,tot = 0,Ans = 0,f[N];
bool cmp(Edge x,Edge y) {return (x.w < y.w) || (x.w == y.w && x.col > y.col) ;}
ll find(ll x) {return f[x] == x ? x : f[x] = find(f[x]);}
void MST(ll mid) {
    tot = 0;Ans = 0;
    for(int i = 1;i <= m;i++) if(e[i].col) e[i].w += mid;
    for(int i = 1;i <= n;i++) f[i] = i;
    sort(e + 1,e + 1 + m,cmp);
    for(int i = 1;i <= m;i++) {
        int x = find(e[i].x),y = find(e[i].y);
        if(find(x) == find(y)) continue;
        Ans += e[i].w;tot += e[i].col;
        f[find(x)] = find(y);
    }
    for(int i = 1;i <= m;i++) if(e[i].col) e[i].w -= mid;
}
int main() {
    n = read();m = read();k = read();
    for(int i = 1;i <= m;i++) {
        e[i].x = read() + 1;e[i].y = read() + 1;
        e[i].w = read();e[i].col = 1 - read();
    }
    ll l = -1e9,r = 1e9,ans = 0;
    while(l <= r) {
        ll mid = l + r >> 1;
        MST(mid);
        if(tot >= k) ans = mid,l = mid + 1;
        else r = mid - 1;
    }
    MST(ans);
    printf("%lld\n",Ans - k * ans);
    return 0;
}

剩下的例题

最后的话