USACO 2025 一月月赛题解

strapplE · 2025-01-28 18:13:20 · 个人记录

我知道你很急。可是比赛还没结束。所以你先别急。

下文更新于 1 月 28 日 21:55。此时比赛已经结束。

T1

回忆版题意：给一张 n\leq 750 的边带权简单无向图。补图也有边权，所有权均为正整数。你要删除一些边，加入一些边，都要付出代价，使得最终的图中有一颗 dfs 树，且 1\sim n 是这棵树的一个合理 dfs 序。最小化代价。

做法：假装最开始一条边都没有，你都要加入，有的边要付出正代价，其它要付出负代价，最后答案加上已有的所有边权之和。接下来做法就呼之欲出了。显然每棵子树对应的点集是一个区间，因此可以考虑 区间 dp。

设 f_{l,r} 表示存在一个以 l 为根的 dfs 树，dfs 序为 l\sim r，只考虑 l\sim r 的导出子图中的所有边，边权和最小值。

不难发现，转移可以通过移除 l 最后一个子节点子树的方式考虑。初始条件是 f_{i,i}=0。因为 f_{i,j} 可以分裂为 f_{i,k}+f_{k+1,j}，只需考虑其它所有边。

因为是 dfs 树，所以只能有返祖边和树边，并且树边一定要被选，因此这个方案的贡献还要加上 a_{i,k+1}+\sum\limits_{x=k+2}^{j}\min(0,a_{i,x})。直接暴力转移就好了，复杂度是常数很小的 O(n^3)，100ms 随便过。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[755][755];
int f[755][755];
int main(){
    int n;
    scanf("%d",&n);
    int he=0;
    for(int i=1;i<=n;++i)for(int j=1;j<i;++j){
        scanf("%d",&a[j][i]);
        if(a[j][i]<0)he+=-a[j][i];
    }
    memset(f,63,sizeof(f));
    for(int i=n;i>=1;--i){
        f[i][i]=0;
        for(int j=i;j<=n;++j){
            int he=max(0,a[i][j+1]);
            for(int k=j+1;k<=n;++k){
                he+=min(0,a[i][k]);
                f[i][k]=min(f[i][k],f[i][j]+f[j+1][k]+he);
            }
        }
    }
    printf("%d\n",he+f[1][n]);
    return 0;
}

T2

回忆版题意：给你一个长度为 n+1 值域为 [0,10^{18}] 的整数序列 p_0,p_1,\dots,p_n。你进行一次操作定义为选择一个下标 y，对所有 p_x 同时减去 |x-y|。求最少操作次数使得所有 p_i 均非正。\sum n\leq 5\times 10^5。

做法：先不说赛时想法了，太唐了，沿着线性规划想了很久居然没找出错（这是因为这个操作数量不是整数或许能更优！），然后从矩阵逆的角度想了很久（以为这是个考虑 \bmod n-1 的数论题？），最后才慢慢步入正解。中间还以为很容易得到一个答案的下界，和正确答案只差常数，还拍了很久，最后才发现假完了。场上也只得到了一个 O(n^2\log V) 的做法，下面说的是赛后完善解法。很遗憾赛时并没有 AK。

观察：两边的位置记为 0 和 n。考虑假如进行了不在两边的两次操作 l\leq r，能否调整呢？

其实是可以的。注意到 |x-l|+|x-r|\leq |x-l+1|+|x+r-1|，因此改为操作 l-1 和 r+1 一定不劣。这启示我们大多数操作办法都是不好的，不为 0 和 n 的操作至多进行一次。因此我们主要关心的只有 0 和 n，设我们在这两个位置上分别进行了 x 次和 y 次操作，中间可能会操作的数为 m。

则序列如果满足以下条件，我们就可以得到一个 x+y+1 次的操作方法（当然去掉这里的 m 部分也成立就 x+y 次了，不过显然更简单不去特意说明）：

看起来是个半平面交状物。但是因为只是要最小化 x+y，不妨设它为 h，那么条件就变成了：

因为 h 具有二分性，多个 \log 无伤大雅就暴力二分。目前 h 是定值，因此对一个 i 来说，除了 x 相关的都是常数（假如我们现在暴力枚举 m），这代表这只是一个对 x 的限制！

模仿联合省选季风的方法，可以算出 x 的一个（整数）下界 L 和（整数）上界 R，如果 L\leq R 则说明这组 (h,m) 合法。如果存在一个 m 满足 (h-1,m) 合法或者去掉 m 且 h 合法，则有一个在 h 步操作内完成的办法！

如果暴力枚举 m，则现在复杂度就是每次二分后再枚举一个 m 再去 O(n) 判断，这也就是我场上的 O(Tn^2logV) 的做法。自闭了。

考虑优化。第一点，中途一个 m 可以被一个 0 和一个 n 拼起来代替。因此即使禁止了中间操作，也有一个至多多一步的优良替代品。那么我们可以在 O(n\log V) 复杂度内找到 ans 和 ans+1 中的一个，只需再判断 ans 是否合法即可。这里复杂度是 O(n^2)。

第二点也就是最后的优化，枚举每个 m 也太慢了吧？对所有 m 一起考虑！因为只有 O(n) 的变化量，感觉对应的 L 和 R 不会差的太大啊？

让我们回顾一下 L 和 R 刚才的求法。因为固定了 h，所以会产生一个常数记作 C_i，也就是 (2i-n)x\geq C_i-|i-m|。2i<n 和 2i>n 显然要分开而且对称，下面只说明其中大的那边。

问题转化成非常多个限制 x\geq \lceil\dfrac{C_i-|i-m|}{2i-n}\rceil。它们求交等价于求最大值，也就是一次操作相当于区间（单点）对一个数取 \max，所有操作做完后复原整个序列。

我们又不难看出，因为上式分子变化量只有 O(n)，所以这个值的变化量只有 O(\dfrac{n}{2i-n})，加起来就是调和级数 O(n\log n)！！！！！所以问题转化成了，区间对一个数取 \max（共 O(n\log n) 次）最后复原序列，采用一个 ST 表“转置”（也有叫“猫树”的）即可以平衡复杂度。

最后总复杂度是什么呢？因为最开始二分要 O(n\log V) 定位到一个差不多的答案。后面这一系列维护也只是一个调和级数复杂度 O(n\log n)，因此总复杂度是 O(\sum n\log nV) 的。当然，第一步二分或许可以用半平面交优化，变成了只用一个排序，复杂度就变成了 O(\sum n\log n)，不过我太菜了，没实现过 HPI，流泪。

代码（目前能过拍，不确定正确性和常数，实现难度适中）：

#include<bits/stdc++.h>
using namespace std;
int n;
long long p[100005];
bool pan(long long h){
    if(h<0)return 0;
    __int128 L=0,R=h;
    for(int i=0;i<=n;++i){
        __int128 c=p[i]-(__int128)h*(n-i);
        if(2*i==n){
            if(0<c)return 0;
            continue;
        }
        if(2*i<n){
            if(c>0)return 0;
            R=min(R,(-c)/(n-2*i));
        }else{
            L=max(L,(c+2*i-n-1)/(2*i-n));
        }
    }
    return L<=R;
}
vector<pair<int,int>>vc;
__int128 xqz(__int128 a,int b){
    return (a-(a%b+b)%b)/b;
}
void fen(__int128 z,int x,int m){
    for(int i=x;i<=n;){
        int j=xqz(z+i-x,m)*m+m-1+x-z;j=min(j,n);
        vc.emplace_back(i,j);
        i=j+1;
    }
    for(int i=x-1;i>=0;){
        int j=z+x-xqz(z+x-i,m)*m-m+1;j=max(j,0);
        vc.emplace_back(j,i);
        i=j-1;
    }
}
void nef(__int128 z,int x,int m){
    for(int i=x;i<=n;){
        int j=x+z-xqz(z-i+x,m)*m;j=min(j,n);
        vc.emplace_back(i,j);
        i=j+1;
    }
    for(int i=x-1;i>=0;){
        int j=xqz(z-x+i,m)*m-z+x;j=max(j,0);
        vc.emplace_back(j,i);
        i=j-1;
    }
}
struct maot{
    long long b[17][100005],a[100005];
    int lg[100005];
    void preinit(){
        lg[1]=0;
        for(int i=2;i<=n+1;++i)lg[i]=lg[i>>1]+1;
    }
    void init(long long x){
        for(int i=0;i<=16;++i)for(int j=0;j<=n;++j)b[i][j]=x;
    }
    inline void gai(int l,int r,long long x){
        int cd=lg[r-l+1];
        b[cd][l]=min(b[cd][l],x);
        b[cd][r-(1<<cd)+1]=min(b[cd][r-(1<<cd)+1],x);
    }
    void solve(){
        for(int i=16;i>=1;--i)for(int j=0;j<=n-(1<<i)+1;++j){
            b[i-1][j]=min(b[i-1][j],b[i][j]);
            b[i-1][j+(1<<(i-1))]=min(b[i-1][j+(1<<(i-1))],b[i][j]);
        }
        for(int i=0;i<=n;++i)a[i]=b[0][i];
    }
}gl,gr;
bool ok(__int128 h){
    if(h<=0)return 0;
    --h;gl.init(-1);gr.init(1+h);
    for(int i=0;2*i<n;++i){
        __int128 c=h*(n-i)-p[i]+n-2*i;
        vc.clear();fen(c,i,n-2*i);
        for(auto pi:vc){
            int j=pi.first,k=pi.second;
            __int128 p=(c+abs(i-j))/(n-2*i);
            if(p<=h){
                gr.gai(j,k,p);
            }
        }
    }
    for(int i=n;2*i>n;--i){
        __int128 c=p[i]-h*(n-i)+4*i-2*n-1;
        vc.clear();nef(c,i,2*i-n);
        for(auto pi:vc){
            int j=pi.first,k=pi.second;
            __int128 p=(c-abs(i-j))/(2*i-n);
            if(p>1){
                gl.gai(j,k,-p);
            }
        }
    }
    gl.solve();gr.solve();
    for(int i=0;i<=n;++i){
        if(n%2==0&&p[n/2]-abs(i-n/2)>h*n/2)continue;
        if(gl.a[i]+gr.a[i]==0)return 1;
    }
    return 0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        --n;
        for(int i=0;i<=n;++i)scanf("%lld",&p[i]);
        int fl=1;
        for(int i=0;i<=n;++i)fl&=(p[i]==0);
        if(fl){
            puts("0");
            continue;
        }
        gl.preinit();gr.preinit();
        long long L=0,R=2e18;
        while(L<=R){
            long long h=(L+R)>>1;
            if(pan(h))R=h-1;
            else L=h+1;
        }
        if(ok(L-1))--L;
        printf("%lld\n",L);
    }
    return 0;
}

T3

回忆版题意：给定两个正整数序列 c_i,w_i。下标分别为 1\sim n-1 和 1\sim n。你可以做任意次以下操作：选择一个 [1,n-1] 的位置 t，并将 w_t 和 w_{t+1} 减去 1，付出 c_t 的代价。求使所有 w_i 降为非正所需的最小代价。要对每个前缀求出同样问题的答案。

做法：首先观察到即使我将操作加强到可以操作任意非负实数次，所需的代价显然不会变，你可以很容易通过一些极端原理来说明。因此可以考虑线性规划（？）,将问题对偶为下面的问题，并不改变难度（完全不理解我为什么要干这个对偶，本质完全相同啊，笑喷）：

给 1\sim n 每个位置赋一个非负整数 d_i，满足以下条件：

并要求最大化 \sum\limits_{i=1}^{n}d_iw_i。

看着很吓人的问题，不过先打个暴力 dp 吧。设 f_{i,j} 表示只考虑前面 i 个数的最优答案（有趣的是，这个 dp 具有前缀性，因此每个前缀的答案同时也能算出，下面我们就只以求整体答案为例！）。可能能得到很少的暴力分，可惜优化没有头猪。因此只能大胆去猜：f_i 看作一个序列的话，它是有凸性的！

不妨认可这个性质是对的。接下来你会做了吗？

无所谓，我们一步一步来！先写出暴力 dp（注意第二维的范围应该限制在 [0,c_{i-1}] 内）：

假如序列有上凸性（即差分单调不增），则我们可以通过 slope trick 的方式只维护斜率，并且可以重新复述下 dp 流程：

1. 把 f_{i-1} 序列改为其前缀最大值。
2. 将 f_{i-1} 的定义域限制在 [0,c_i] 内。
3. 将 f_{i-1} 序列翻转得到目前暂时的 f_i。
4. 对所有 j，将 f_{i,j} 加上 w_ij。
5. 求出答案，也就是 f_i 的前缀最大值。

接下来对应到差分序列上（注意它单调不增，且可以把相邻相等的捏到一起）：

1. 删掉后缀所有 <0 的数，把不足的补 0。
2. 如果目前总长超过了限制，删掉一段后缀，否则补 0。
3. 翻转并取反。
4. 整体加 w_i。
5. 同时记录下 f_{i,0} 点处的值，则答案为这个值加上序列中所有 >0 的数的和。

接下来我们考虑维护标记：fl,A,B 分别表示是否翻转，序列中一个数 x 实际对应的值是 Ax+B。再维护值 f0,h1,he 表示最前面的点值，序列中值的个数，以及和。则可以考虑用双端队列维护，并从任意一个方向添加或弹出一些值。

考虑如何使这些标记封闭：

1. 加一个数 x 等价于在序列中添加一个 A(x-B)，注意这里 A\in \{1,-1\}。
2. 翻转对应 fl 取反。值取反等价于将 A,B 取反。此时 f0 要加上 he，且 he 也要取反。
3. 整体加等价于 B 加。
4. 最后一个小问题，求答案的时候，难不成还要维护前缀和吗？其实不用，这是因为，这些 \leq 0 的数在考虑下一个位置时的第一个操作中，也会被弹掉了。因此可以和下一次第一个操作放一起做。

复杂度均摊线性，看我们多么厉害！居然可以 O(n) 解决这个题，数据结构只需要一个双端队列，不比神秘平衡树优美多了？

此外，这个题目也表明如下一个观点：遇到类似线性规划的问题可能会有很多种办法，急着对偶未必是一个好的选择！

代码：

#include<bits/stdc++.h>
using namespace std;
int w[500005],c[500005];
deque<pair<int,long long>>dq;
long long A=1,B=0;
int fl=0;
long long h1,he;
long long f0;
void pback(int x,long long y){
    h1+=x;he+=x*y;
    if(fl==0)dq.emplace_back(x,(y-B)/A);
    else dq.emplace_front(x,(y-B)/A);
}
void zhej(long long y){
    he+=y*h1;B+=y;
}
void rev(){
    fl^=1;f0+=he;
    A*=-1,B*=-1;he=-he;
}
void qian(){
    while(dq.size()){
        if(fl==0){
            if(A*dq.back().second+B<=0){
                auto pi=dq.back();dq.pop_back();
                he-=pi.first*(A*pi.second+B);
                h1-=pi.first;
            }else break;
        }else{
            if(A*dq.front().second+B<=0){
                auto pi=dq.front();dq.pop_front();
                he-=pi.first*(A*pi.second+B);
                h1-=pi.first;
            }else break;
        }
    }
}
void resz(int m){
    if(h1<m){
        pback(m-h1,0);
    }else while(h1>m){
        pair<int,long long>pi;
        if(fl==0)pi=dq.back(),dq.pop_back();
        else pi=dq.front(),dq.pop_front();
        he-=pi.first*(A*pi.second+B);
        h1-=pi.first;
        if(h1>=m)continue;
        pback(m-h1,A*pi.second+B);
    }
}
void suanqian(){
    while(dq.size()){
        if(fl==0){
            if(A*dq.back().second+B<=0){
                auto pi=dq.back();dq.pop_back();
                he-=pi.first*(A*pi.second+B);
                h1-=pi.first;
            }else break;
        }else{
            if(A*dq.front().second+B<=0){
                auto pi=dq.front();dq.pop_front();
                he-=pi.first*(A*pi.second+B);
                h1-=pi.first;
            }else break;
        }
    }
    printf("%lld\n",f0+he);
}
void output(){
    printf("!!! %lld\n",f0);
    printf("? %d %lld %lld\n",fl,A,B);
    printf("%lld %lld\n",h1,he);
    int gs=0;long long g2=0;
    for(auto pi:dq){
        int T=pi.first;
        gs+=pi.first;
        while(T--)printf("%lld ",A*pi.second+B);
        g2+=pi.first*(A*pi.second+B);
    }
    cout<<gs<<" "<<g2<<endl;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&w[i]);
    for(int i=2;i<=n;++i)scanf("%d",&c[i]);
    f0=0;pback(c[2],w[1]);qian();
    for(int i=2;i<=n;++i){
        resz(c[i]);
        rev();
        zhej(w[i]);
        suanqian();
    }
//  output();
    return 0;
}

本文完稿于 1 月 28 日 23:02 分。