专栏文章

尼罗河题解

MMutU
P11049题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipds9lx
此快照首次捕获于
2025/12/03 10:21
3 个月前
此快照最后确认于
2025/12/03 10:21
3 个月前
查看原文
题目传送门
刚看到这题的时候还是紫，过了二十分钟降蓝了。
考虑 O(nq)O(nq) 做法。我们把所有货物按照 ww 排序，令 fif_i 为前 ii 个全部运走所需的最小代价。
注意到一个性质：如果把所有两两配对的货物视为一条线段，在最优情况下这些线段一定能够不相交。假设两两有相交，将四个点中左边两个和右边两个连一起显然合法且等价。
注意到另一个性质：如果把所有两两配对的货物视为一条线段，在最优情况下这些线段长度不会超过 33。也就是说一个货物最多只需要考虑前两个货物。假设与前面第三个货物配对，将这个点以及前三个点左边两个连一起显然合法且等价。
于是递推式:
fi={fi−1+aiwi−wi−1>dmin⁡(fi−1+ai,fi−2+bi−1+bi)wi−wi−1≤dmin⁡(fi−1+ai,fi−2+bi−1+bi,fi−3+bi−2+ai−1+bi)wi−wi−2≤df_i = \begin{cases} f_{i-1}+a_i & w_i-w_{i-1}>d \\ \min(f_{i-1}+a_i,f_{i-2}+b_{i-1}+b_i) & w_i-w_{i-1}\le d\\ \min(f_{i-1}+a_i,f_{i-2}+b_{i-1}+b_i,f_{i-3}+b_{i-2}+a_{i-1}+b_i) & w_i-w_{i-2}\le d \\ \end{cases}
考虑优化。注意到询问可以离线出来，按照 dd 排序。
这样转移的限制越来越宽，每个位置的转移式子也会变化。但是这些变化的总数是 O(n)O(n) 级别的。
考虑维护每个式子变化的时间。把每个 ii 分别按照 wi−wi−1w_i-w_{i-1} 和 wi−wi−2w_i-w_{i-2} 从小到大排序，能够快速求出对于某个询问哪些式子会改变。
我们把转移抽象成广义矩阵乘法。其中把乘法操作变为加法，加法操作变为取 min⁡\min。即：
CPP
matrix operator * (matrix a,matrix b){
    matrix ans;
    ans.init1(3,3);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                ans.a[i][j]=min(ans.a[i][j],a.a[i][k]+b.a[k][j]);
            }
        }
    }
    return ans;
}
因为需要考虑前两个位置，矩阵边长为 33。
三个转移对应的矩阵乘分别为：
[ai+∞+∞0+∞+∞+∞0+∞][fi−1fi−2fi−3]=[fifi−1fi−2]\begin{bmatrix} a_i & +\infty & +\infty \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i \\ f_{i-1} \\ f_{i-2} \end{bmatrix}
[aibi+bi−1+∞0+∞+∞+∞0+∞][fi−1fi−2fi−3]=[fifi−1fi−2]\begin{bmatrix} a_i & b_i+b_{i-1} & +\infty \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i \\ f_{i-1} \\ f_{i-2} \end{bmatrix}
[aibi+bi−1bi+ai−1+bi−20+∞+∞+∞0+∞][fi−1fi−2fi−3]=[fifi−1fi−2]\begin{bmatrix} a_i & b_i+b_{i-1} & b_i+a_{i-1}+b_{i-2} \\ 0 & +\infty & +\infty \\ +\infty & 0 & +\infty \end{bmatrix} \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{bmatrix} = \begin{bmatrix} f_i \\ f_{i-1} \\ f_{i-2} \end{bmatrix}
能够证明这种运算具有结合率。
线段树维护每个式子，单点修改 O(n)O(n) 次，复杂度 O(nlog⁡n)O(n \log n)。最后根节点就是答案。
细节见代码部分。

Code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100100;
struct matrix{
    int n,m;
    long long a[3][3];
    inline void init0(int x,int y){
        n=x,m=y;
        for(int i=0;i<n;i++) for(int j=0;j<m;j++) a[i][j]=0;
        return;
    }
    inline void init1(int x,int y){
        n=x,m=y;
        for(int i=0;i<n;i++) for(int j=0;j<m;j++){
            a[i][j]=1e18;
        }
        return;
    }
    inline void print(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) cout<<a[i][j]<<' ';
            cout<<'\n';
        }
    }
};
matrix operator * (matrix a,matrix b){
    matrix ans;
    ans.init1(3,3);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                ans.a[i][j]=min(ans.a[i][j],a.a[i][k]+b.a[k][j]);
            }
        }
    }
    return ans;
}
struct node{
    int w,a,b;
}p[N];
struct ask{
    int id,d;
}e[N];
int ans[N];
int n,q;
vector <long long> res;
long long w[N],a[N],b[N];
bool cmp(ask a,ask b){
    return a.d<b.d;
}
matrix tree[N*4];
inline void push_up(int x){
    tree[x]=tree[x*2+1]*tree[x*2];
}
int f1,f2;
inline void build(int l,int r,int x){
    if(l==r){
        tree[x].init1(3,3);
        tree[x].a[0][0]=a[l];
        tree[x].a[1][0]=0;
        tree[x].a[2][1]=0;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    push_up(x);
    return;
}
matrix d;
inline void updata(int l,int r,int id,int x){
    if(l>id || r<id) return;
    if(l>=id && r<=id){
        if(l==2){
            tree[x].a[0][0]=f2;
            tree[x].a[1][0]=f1;
            tree[x].a[2][0]=0;
            return;
        }
        tree[x]=d; 
        return;
    }
    int mid=l+r>>1;
    if(mid>=id) updata(l,mid,id,x*2);
    if(mid+1<=id) updata(mid+1,r,id,x*2+1);
    if(l==1 && r==2) tree[x]=tree[x*2+1]; else push_up(x);
    return;
}
bool cmp0(node a,node b){
    return a.w<b.w;
}
vector <pair <int,int> > v1,v2;
std::vector<long long> calculate_costs(
std::vector<signed> W, std::vector<signed> A, 
std::vector<signed> B, std::vector<signed> E){
    n=W.size(),q=E.size();
    for(int i=1;i<=n;i++) p[i].a=A[i-1],p[i].b=B[i-1],p[i].w=W[i-1];
    sort(p+1,p+1+n,cmp0);
    for(int i=2;i<=n;i++) v1.push_back({p[i].w-p[i-1].w,i});
    for(int i=3;i<=n;i++) v2.push_back({p[i].w-p[i-2].w,i});
    for(int i=1;i<=n;i++) a[i]=p[i].a,b[i]=p[i].b,w[i]=p[i].w;
    for(int i=1;i<=q;i++) e[i].d=E[i-1],e[i].id=i;
    sort(e+1,e+1+q,cmp);
    sort(v1.begin(),v1.end()),sort(v2.begin(),v2.end());
    build(1,n,1);
    int x=0,y=0;
    for(int i=1;i<=q;i++){
        f1=a[1];
        if(w[2]-w[1]<=e[i].d) f2=b[1]+b[2];
        else f2=a[1]+a[2];
        updata(1,n,2,1);
        d.init1(3,3);
        d.a[1][0]=0;
        d.a[2][1]=0;
        while(x<n-1 && v1[x].first<=e[i].d){
            int j=v1[x].second;
            d.a[0][0]=a[j];
            d.a[0][1]=b[j]+b[j-1];
            updata(1,n,v1[x].second,1),++x;
        } 
		while(y<n-1 && v2[y].first<=e[i].d){
            int j=v2[y].second;
            d.a[0][0]=a[j];
            d.a[0][1]=b[j]+b[j-1];
            d.a[0][2]=b[j]+b[j-2]+a[j-1];
            updata(1,n,v2[y].second,1),++y;
        }
        ans[e[i].id]=tree[1].a[0][0];
    }
    for(int i=1;i<=q;i++) res.push_back(ans[i]);
    return res;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...