Educational Codeforces Round 144（CF1796 D~E）题解-526互联

D. Maximum Subarray

十分钟秒了一道 *2000，非常爽，但是个人感觉确实非常简单。

下面令 \(b_i=a_{i}-x\)，\(b_i'=a_i+x\) 。

因为 \(k<=20\)，因此考虑一个复杂度与 \(k\) 相关的做法。

不妨 dp：设 \(f_{i,j,0/1}\) 表示考虑了前 \(i\) 个数，对 \(j\) 个数加上了 \(x\)，第 \(i\) 个数不加/加，且强制选择第 \(i\) 个数的情况下的最大子段和。

转移是平凡的，就类似于正常的求最大子段和：

\[\begin{aligned} f_{i,j,0}&=\max(b_i,f_{i-1,j,0}+b_i,f_{i-1,j,1}+b_i) \\ f_{i,j,1}&=\max(b_i',f_{i-1,j-1,0}+b_i',f_{i-1,j-1,1}+b_i') \end{aligned} \]

对所有满足 \(n-i\ge k-j\) 的 \(f_{i,j,0/1}\) 统计答案即可，实现时注意一些边界条件。

时间复杂度 \(O(nk)\)。

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+5;
int n,k,x,a[N],f[N][22][2];
void Main(){
    cin>>n>>k>>x;
    For(i,1,n) cin>>a[i];
    int ans=0;
    For(i,1,n) For(j,0,min(i,k)){
        int a1=a[i]-x,a2=a[i]+x;
        if(i!=j) f[i][j][0]=max({a1,f[i-1][j][0]+a1,f[i-1][j][1]+a1});
        if(j) f[i][j][1]=max({a2,f[i-1][j-1][0]+a2,f[i-1][j-1][1]+a2});
        if(n-i>=k-j) ans=max({ans,f[i][j][0],f[i][j][1]});
    }
    cout<<ans<<'\n';
    For(i,1,n) For(j,0,k) f[i][j][0]=f[i][j][1]=0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;cin>>T;
    while(T--) Main();
    return 0;
}

E. Colored Subgraphs

题目链接

看出来了换根 dp，但是完全不会实现。

我们不妨手模一下题目中对染色的限制条件，不难发现等价于以 \(r\) 为根时对树进行链剖分，代价为最短链的点数。

那么先考虑固定以 \(1\) 为根时怎么做，假设对于所有的儿子我们已经染好了色，那么贪心地想，我们肯定会把当前点染成儿子中长度最短的那个颜色，这样一定是最优的，而次小的以及更大的链长度就被定住了，此时会影响答案的就是当前点的儿子中次小的那个。

我们对每个点 \(u\) 维护一个 \(f_u\) 表示 \(u\) 的所有儿子所在的链的长度集合，那么答案即为所有 \(f_u\) 的次小值以及 \(f_1\) 的最小值加一之间的最小值。

考虑换根，将根从 \(u\) 换到 \(v\) 的过程其实就类似于，删除 \(v\) 对 \(f_u\) 的贡献，加入 \(u\) 对 \(f_v\) 的贡献，这个可以使用 multiset 简单维护，回溯的过程中及时撤销即可。

时间复杂度 \(O(n\log n)\)。

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+5;
const int inf=1e18;
int n,ans;
multiset<int>f[N],g;
vector<int>G[N];
int get(int now){
    if(!f[now].size()) return 1;
    return (*f[now].begin())+1;
}
void ins(int now,int val){
    if(f[now].size()>=2) g.erase(g.find(*next(f[now].begin())));
    f[now].insert(val);
    if(f[now].size()>=2) g.insert(*next(f[now].begin()));
}
void del(int now,int val){
    if(f[now].size()>=2) g.erase(g.find(*next(f[now].begin())));
    f[now].erase(f[now].find(val));
    if(f[now].size()>=2) g.insert(*next(f[now].begin()));
}
void dfs1(int now,int fa){
    for(int to:G[now]){
        if(to==fa) continue;
        dfs1(to,now);
        f[now].insert(get(to));
    }
    if(f[now].size()>=2) g.insert(*next(f[now].begin()));
}
void dfs2(int now,int fa){
    ans=max(ans,min(get(now),g.empty()?inf:*g.begin()));
    for(int to:G[now]){
        if(to==fa) continue;
        del(now,get(to));
        ins(to,get(now));
        dfs2(to,now);
        del(to,get(now));
        ins(now,get(to));
    }
}
void Main(){
    cin>>n;g.clear();ans=0;
    For(i,1,n) f[i].clear(),G[i].clear();
    For(i,1,n-1){
        int u,v;cin>>u>>v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs1(1,0);dfs2(1,0);
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;cin>>T;
    while(T--) Main();
    return 0;
}