XCPC Notes

Appearance

发布时间：2025-05-03

wqs二分 ​

模型介绍 ​

  • 限制选择kk个物品，最大化收益；不限制条件的情况下，最大值能快速求出来
  • 设恰好选择kk个物品收益为gkg_k，这是一个上凸壳，即 gk+1−gk≤gk−gk−1g_{k+1}-g_{k} \leq g_{k}-g_{k-1}
  • 二分斜率cc，g(x)=cx+bg(x)=cx+b与凸包相切时，截距bb最大，b=g(x)−cxb=g(x)-cx，可以看成每选一个物品就要多cc的代价
  • 在无限制的情况下求出，最大收益对应的xx,x>=k增大mid，否则减少
  • 如果(k,g[k])在上凸壳左半部分(斜率大于等于0)，那么答案就一定对
  • 如果在右半部分(斜率小于0)，需要设定二分边界
  • 设下界为11，上界根据gi−gi−1g_i-g_{i-1}的最大值设置，如果二分查找的值严格小于kk，那么说明交易次数的限制并不是瓶颈，而价格才是
  • 如果上凸壳上有若干连续的且斜率相等的线段，会对应多个不同的kk,此时设定在满足gmidg_{mid}最大时，xx最小，那么即使x≠kx \ne k，b+mid⋅kb+mid \cdot k，仍然是答案
  • 如果是下凸壳(最小化收益)则无需管答案是否合法，因为一定能二分到，此时b−mid⋅kb-mid \cdot k才是答案

总结：

当为下凸壳时，每个物品添加代价，总答案减去斜率代价；二分上下界都尽可能大
当为上凸壳时，每个物品减少代价，总答案加上斜率代价；考虑左半边和右半边，如果答案在左半边，下界为1

P2619 [国家集训队] Tree I(wqs二分下凸壳板子) ​

给你一个无向带权连通图，每条边是黑色或白色。求恰好包含kk条白边的最小生成树

  • 假设没有限制，最小值在xx处取
  • k<xk \lt x时，那么每次选的白边肯定越来越大，下降速率肯定变慢
  • k>xk \gt x时，此时白边已经饱和，强行更换白边值会越来越大，并且仍然满足优先选值更小的白边替换，那么增加速率肯定是增大的
  • 因此是一个下凸壳
  • 如果要求输出方案，同样的边权，如果已经选够k条，则优先选择黑边；否则优先选择白边
cpp
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<array<int,4>> e;
    for(int i=0;i<m;i++){
        int u,v,w,c;
        cin>>u>>v>>w>>c;
        e.push_back({w,u,v,c});
    } 
    DSU dsu;
    auto check=[&](int mid){
        dsu.init(n+1);
        for(auto &[w,u,v,c]:e){
            if(c==0)w+=mid;
        }
        ranges::sort(e,[&](auto a,auto b){
            if(a[0]!=b[0])return a[0]<b[0];
            return a[3]<b[3];
        });
        int used=0,ans=0;
        for(auto [w,u,v,c]:e){
            if(dsu.merge(u,v)){
                used+=c==0;
                ans+=w;
            }
        }
        for(auto &[w,u,v,c]:e){
            if(c==0)w-=mid;
        }
        return PII{used,ans};
    };
    int l=-100,r=100;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid).F>=k)l=mid;
        else r=mid-1;
    }
    auto [used,ans]=check(l);
    cout<<ans-l*k<<"\n";
}

满足ss编号的点度数为kk的情况

cpp
void solve(){
    int n,m,s,k;
    cin>>n>>m>>s>>k;
    vector<array<int,4>> e;
    for(int i=0;i<m;i++){
        int u,v,w,c;
        cin>>u>>v>>w;
        c=!(u==s||v==s);
        e.push_back({w,u,v,c});
    } 
    DSU dsu;
    dsu.init(n+1);
    for(auto [w,u,v,c]:e){
        dsu.merge(u,v);
    }
    if(dsu.size(s)!=n){
        cout<<"Impossible\n";
        return;
    }
    auto check=[&](int mid){
        dsu.init(n+1);
        for(auto &[w,u,v,c]:e){
            if(c==0)w+=mid;
        }
        ranges::sort(e,[&](auto a,auto b){
            if(a[0]!=b[0])return a[0]<b[0];
            return a[3]<b[3];
        });
        int used=0,ans=0;
        for(auto [w,u,v,c]:e){
            if(dsu.merge(u,v)){
                used+=c==0;
                ans+=w;
            }
        }
        for(auto &[w,u,v,c]:e){
            if(c==0)w-=mid;
        }
        return PII{used,ans};
    };
    int l=-1e9,r=1e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid).F>=k)l=mid;
        else r=mid-1;
    }
    // 优先使用都无法到达k，或者优先不使用超过k，都是不合法的
    if(check(-1e9).F<k||check(1e9).F>k){
        cout<<"Impossible\n";
        return;
    }
    auto [used,ans]=check(l);
    cout<<ans-l*k<<"\n";
}

P1484 种树 ​

nn个点种最多kk棵树的最大利益，相邻两个位置只能种一个

cpp
void chmax(PII &a,PII b){
    if(a.F<b.F)a=b;
    else if(a.F==b.F&&a.S<b.S)a.S=b.S;
}
PII operator+(PII a,PII b){
    return {a.F+b.F,a.S+b.S};
}
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector f(n+1,vector<PII>(2));
    auto check=[&](int mid){
        for(int i=0;i<=n;i++){
            for(int j=0;j<2;j++)f[i][j]={-INF,0};
        }
        f[0][0]={0,0};
        for(int i=1;i<=n;i++){
            chmax(f[i][0],f[i-1][0]);
            chmax(f[i][0],f[i-1][1]);
            chmax(f[i][1],f[i-1][0]+PII{a[i]-mid,1});
        }
        return max(f[n][0],f[n][1]);
    };
    auto [res,cnt]=check(0);
    if(cnt<=k){
        cout<<res<<"\n";
        return;
    }
    int l=1,r=1e6+10;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid).S>=k)l=mid;
        else r=mid-1;
    }
    auto [res1,cnt1]=check(l);
    cout<<res1+l*k<<"\n";
}

P4767 [IOI 2000] 邮局 加强版 ​

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

可以O(n2)O(n^2)预处理出在[l,r][l,r]放一个邮局的最小代价，那么假设没有限制放邮局，有一个朴素的O(n2)O(n^2)dp做法

二分斜率(理论斜率应该为负，但是只有正斜率才有效，很奇怪)

cpp
void chmin(PII &a,PII b){
    if(a.F>b.F)swap(a,b);
    else if(a.F==b.F)a.S=max(a.S,b.S);
}
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    vector w(n+1,vector<int>(n+1));
    for(int l=1;l<=n;l++){
        w[l][l]=0;
        for(int r=l+1;r<=n;r++)w[l][r]=w[l][r-1]+a[r]-a[(l+r)/2];
    }
    vector<PII> dp(n+1);
    auto check=[&](int mid){
        dp.assign(n+1,{INF,0});
        dp[0]={0,0};
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++)chmin(dp[i],{dp[j].F+w[j+1][i]+mid,dp[j].S+1});
        }
        return dp[n];
    };
    int l=-3e7,r=3e7;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid).S>=k)l=mid;
        else r=mid-1;
    }
    auto [ans,cnt]=check(l);
    cout<<ans-l*k<<"\n";
}

P3354 [IOI 2005] Riv 河流 ​

几乎整个 Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫 Bytetown。

在 Byteland 国，有 nn 个伐木的村庄，这些村庄都座落在河边。目前在 Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到 Bytetown 的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造 kk 个伐木场。这 kk 个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到 Bytetown 了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。

注：所有的河流都不会分叉，形成一棵树，根结点是 Bytetown。

国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米 11 分钱。

  • 对于 50%50\% 的数据，保证 n≤20n\le 20。
  • 对于 100%100\% 的数据，保证 2≤n≤1002\le n\le 100，1≤k≤min⁡(n,50)1\le k\le \min(n,50)，0≤vi≤n0\le v_i\le n，0≤wi≤1040\le w_i\le 10^4，1≤di≤1041\le d_i\le 10^4。
  • 保证每年所有的木料流到 bytetown 的运费不超过 2×1092\times 10^9 分。

思路：

  • 考虑每多建一个厂，就会增加mid的代价
  • 定义fi,j,0/1f_{i,j,0/1}表示当前节点为ii，有伐木场的最近祖先为jj，当前节点是否建伐木场的最小代价
  • 注意fu,u,0f_{u,u,0}是非法状态
  • 考虑如何转移，如果当前不建伐木场，那么 fu,j,0=∑min⁡(fv,j,0,fv,j,1)f_{u,j,0}=\sum \min(f_{v,j,0},f_{v,j,1})
  • 否则 fu,j,1=∑min⁡(fv,u,0,fv,u,1)f_{u,j,1}= \sum \min(f_{v,u,0},f_{v,u,1})，vv的木头全部到uu
  • 然后考虑当前节点的贡献，显然 fu,j,0+=wu(depu−depj)f_{u,j,0}+=w_u(dep_u-dep_j)(加上运输木头的代价),fu,j,1+=midf_{u,j,1}+=mid(建厂的代价)
  • 假设根节点有场，答案就是f0,0,1−midf_{0,0,1}-mid，同时保证相同答案选择建更多的场
  • wqs二分，一定可以卡出答案
cpp
void chmin(PII &a,PII b){
    if(a.F>b.F)swap(a,b);
    else if(a.F==b.F)a.S=max(a.S,b.S);
}
void add(PII &a,PII b){
    a.F+=b.F;
    a.S+=b.S;
}
PII min(PII a,PII b){
    if(a.F<b.F||(a.F==b.F&&a.S>b.S))return a;
    return b;
}
void solve(){
    int n,k;
    cin>>n>>k;
    vector<PII> adj[n+1];
    vector<int> w(n+1);
    for(int i=1;i<=n;i++){
        cin>>w[i];
        int p,d;
        cin>>p>>d;
        adj[p].emplace_back(i,d);
        adj[i].emplace_back(p,d);
    }
    vector<int> dep(n+1),stk(n+1);
    int top=0;
    vector f(n+1,vector (n+1,vector<PII>(2)));
    function<void(int,int,int,int)> dfs=[&](int u,int fa,int d,int mid){
        dep[u]=d;
        stk[++top]=u;
        for(auto [v,w]:adj[u]){
            if(v==fa)continue;
            dfs(v,u,d+w,mid);
            for(int i=1;i<=top;i++){
                int j=stk[i];
                if(i!=top){
                    add(f[u][j][0],min(f[v][j][0],f[v][j][1]));
                }
                add(f[u][j][1],min(f[v][u][0],f[v][u][1]));
            }
        }
        for(int i=1;i<=top;i++){
            int j=stk[i];
            if(i!=top)f[u][j][0].F+=w[u]*(dep[u]-dep[j]);
            f[u][j][1].F+=mid;
            f[u][j][1].S++;
        }
        top--;
    };
    auto check=[&](int mid){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                for(int x=0;x<2;x++)f[i][j][x]={0,0};
            }
        }
        dfs(0,-1,0,mid);
        return PII{f[0][0][1].F-mid,f[0][0][1].S-1};
    };
    int l=1,r=2e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid).S>=k)l=mid;
        else r=mid-1;
    }
    auto [res,cnt]=check(l);
    cout<<res-l*k<<"\n";
}

P4072 [SDOI2016] 征途 ​

nn个数，分成mm段，求方差vv最小，输出vm2vm^2

思路：

  • 首先可以化简式子为 m∑x2−S2m\sum x^2 - S^2，SS为总和，xx为每段的大小
  • 显然是下凸壳
  • 直接朴素dp转移即可，复杂度 O(n2log⁡V)O(n^2 \log V),斜率优化为 O(nlog⁡V)O(n \log V)

P4983 忘情 ​

和上题一样，求分割mm段，最小化 ∑(x+1)2\sum (x+1)^2的值

但是此题范围很大，需要斜率优化

dpi=dpj+(Si−Sj+1)2dp_i=dp_j+(S_i-S_j+1)^2，移项得 dpj+Sj2−2Sj=dpi−(Si+1)2+2SiSjdp_j+S_j^2-2S_j=dp_i-(S_i+1)^2+2S_iS_j

  • b=dpi−(Si+1)2,k=2Sib=dp_i-(S_i+1)^2,k=2S_i，每个点为 (Sj,dpj+Sj2−2Sj)(S_j,dp_j+S_j^2-2S_j)
  • 特殊注意，优先使用分段最多的状态
cpp
void chmin(PII &a,PII b){
    if(a.F>b.F)swap(a,b);
    else if(a.F==b.F)a.S=max(a.S,b.S);
}
void add(PII &a,PII b){
    a.F+=b.F;
    a.S+=b.S;
}
PII min(PII a,PII b){
    if(a.F<b.F||(a.F==b.F&&a.S>b.S))return a;
    return b;
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1),sum(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    vector<PII> dp(n+1);
    vector<int> q(n+1);
    auto check=[&](int mid){
        for(int i=1;i<=n;i++)dp[i]={INF,0};
        dp[0]={0,0};
        auto Y=[&](int i){
            return dp[i].F+sum[i]*sum[i]-2*sum[i];
        };
        auto X=[&](int i){
            return sum[i];
        };
        auto cmp=[&](int x,int y){
            if(x>y)return 1;
            if(x<y)return -1;
            return 0;
        };
        int hh=0,tt=0;
        q[0]=0;
        for(int i=1;i<=n;i++){
            while(hh<tt){
                int c=cmp(Y(q[hh+1])-Y(q[hh]),2*sum[i]*(X(q[hh+1])-X(q[hh])));
                if(c<0)hh++;
                else if(c==0&&dp[q[hh+1]].S>dp[q[hh]].S)hh++;
                else break;
            }
            int j=q[hh];
            chmin(dp[i],{dp[j].F+(sum[i]-sum[j]+1)*(sum[i]-sum[j]+1)+mid,dp[j].S+1});
            while(hh<tt){
                int c=cmp((Y(q[tt])-Y(q[tt-1]))*(X(i)-X(q[tt])),(Y(i)-Y(q[tt]))*(X(q[tt])-X(q[tt-1])));
                if(c>0)tt--;
                else if(c==0&&dp[i].S>=dp[q[tt]].S)tt--;
                else break;
            }
            q[++tt]=i;
        }
        return dp[n];
    };
    int l=-1e16,r=1e16;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid).S>=m)l=mid;
        else r=mid-1;
    }
    auto [res,cnt]=check(l);
    cout<<res-l*m<<"\n";
}

CF321E Ciel and Gondolas ​

决策单调性，待补。。。

P5308 [COCI 2018/2019 #4] Akvizna ​

你面临 nn 名参赛者的挑战，最终要将他们全部战胜。
每一轮中，都会淘汰一些选手；你会得到这一轮奖金池中 被淘汰者 除以 这一轮对手总数 比例的奖金。

例如某一轮有 1010 个对手，淘汰了 33 个，那么你将获得奖金池中 3/103/10 的奖金。

假设每一轮的奖金池均为一元，Mirko 希望通过恰好 kk 轮赢得比赛，那么他最多可能获得多少奖金呢？

你只需要输出答案保留 99 位小数即可。

对于20%20\%的数据，1≤n≤1001\le n\le 100。

对于40%40\%的数据，1≤n≤30001\le n \le 3000。

对于100%100\%的数据，1≤k≤n≤1051\le k \le n \le 10^5。

本题较卡精度，请留意。

  • 上凸壳
  • 考虑如何求 dpi=dpj+i−jn−jdp_i=dp_j+\frac{i-j}{n-j}，dpj−jn−j=dpi+(−i)1n−jdp_j-\frac{j}{n-j}=dp_i+(-i)\frac{1}{n-j}
  • 可以斜率优化
cpp
const double eps=1e-14;  
int cmp(double x,double y){
    if(fabs(x-y)<eps)return 0;
    return x<y?-1:1;
}
void chmax(PDI &a,PDI b){
    int o=cmp(a.F,b.F);
    if(o<0)swap(a,b);
    else if(o==0)a.S=max(a.S,b.S);
}
void solve(){
    int n,k;
    cin>>n>>k;
    vector<PDI> dp(n+1);
    vector<int> q(n+1);
    auto check=[&](double mid){
        for(int i=1;i<=n;i++)dp[i]={-INF,0};
        dp[0]={0,0};
        int hh=0,tt=0;
        q[0]=0;
        auto Y=[&](int i){
            return dp[i].F-1.0*i/(n-i);
        };
        auto X=[&](int i){
            return 1.0/(n-i);
        };
        for(int i=1;i<=n;i++){
            while(hh<tt){
                int c=cmp((Y(q[hh+1])-Y(q[hh]))/(X(q[hh+1])-X(q[hh])),-1.0*i);
                if(c>0)hh++;
                else if(c==0&&dp[q[hh+1]].S>dp[q[hh]].S)hh++;
                else break;
            }
            int j=q[hh];
            chmax(dp[i],{dp[j].F+1.0*(i-j)/(n-j)-mid,dp[j].S+1});
            while(hh<tt){
                int c=cmp((Y(q[tt])-Y(q[tt-1]))/(X(q[tt])-X(q[tt-1])),(Y(i)-Y(q[tt]))/(X(i)-X(q[tt])));
                if(c<0)tt--;
                else if(c==0&&dp[q[tt]].S<dp[i].S)tt--;
                else break;
            }
            q[++tt]=i;
        }
        return dp[n];
    };
    double l=0,r=1e18;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(check(mid).S>=k)l=mid;
        else r=mid;
    }
    auto [res,cnt]=check(l);
    cout<<fixed<<setprecision(9);
    cout<<res+l*k<<"\n";
}

Wenwei Lin · 2022 — 2025