Educational Codeforces Round 158 (Rated for Div. 2)

https://codeforces.com/contest/1901

C. Add, Divide and Floor

题意

给定一个长度为 $n$ 的数组 $a$，每次操作可以选择一个数 $x$，然后对所有的 $a_i$，令 $a_i\leftarrow \lfloor\dfrac{a_i+x}{2}\rfloor$。求最小操作次数使得 $a$ 中每个元素都相等。

数据范围：$1\leq n\leq 2\times10^5,0\leq a_i\leq 10^9$。

题解

首先 $x$ 的任何取值可以等价为 $0$ 或 $1$。然后只要保证最大值和最小值相等即可，为此，我们根据最小值进行贪心，当它为奇数时选择 $1$，偶数时选择 $0$。可以理解为我们优先保证最小值尽可能慢地减小，然后保证最大值尽可能快地减小，这是最优的。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        vector<int> ans;
        while(1)
        {
            if(a[n]-a[1]==0) break;
            else
            {
                if(a[1]&1) 
                {
                    ans.push_back(1);
                    for(int i=1;i<=n;i++) a[i]=(a[i]+1)/2;
                }
                else
                {
                    ans.push_back(0);
                    for(int i=1;i<=n;i++) a[i]=a[i]/2;
                }
            }
        }
        int k=(int)ans.size();
        cout<<k<<'\n';
        if(k<=n)
        {
            for(int i=1;i<=k;i++) cout<<ans[i-1]<<" \n"[i==k];
        }
    }
    return 0;
}

E. Compressed Tree

题意

给定一棵树，可以先删除一些度数为 $1$ 的结点。然后不断地删除度数为 $2$ 的结点，并将两个相邻结点连边。求剩下所有结点权值之和的最大值。

题解

令 $dp_u$ 表示以 $u$ 为根的子树内能作为一个最终不被删掉整体的最大权值和。转移参考代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) cin >> a[i];
        vector<vector<int> > g(n + 1);
        for(int i = 0; i < n - 1; i++){
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        LL ans = 0;
        
        vector<LL> dp(n + 1);

        auto dfs = [&](auto &&dfs, int u, int fa) -> void {
            ans = max(ans, 1LL * a[u]);
            dp[u] = a[u];
            vector<LL> v1, v2;
            for(auto j : g[u]){
                if (j == fa) continue;
                dfs(dfs, j, u);
                if (dp[j] >= 0) v1.push_back(dp[j]);
                else v2.push_back(dp[j]);
            }
            sort(v1.begin(), v1.end());
            sort(v2.begin(), v2.end());
            // 链中的一点
            if (!v1.empty()){
                dp[u] = max(dp[u], v1.back());
                ans = max(ans, v1.back() + a[u]);
            }
            if (!v2.empty()){
                dp[u] = max(dp[u], v2.back());
                ans = max(ans, v2.back() + a[u]);
            }
            // 有多个子树
            if (v1.size() > 1){
                LL s = a[u];
                for(auto x : v1) s += x;
                dp[u] = max(dp[u], s);
                ans = max(ans, v1.back() + v1[v1.size() - 2]);
                if (v1.size() > 2){
                    ans = max(ans, s);
                }
            }
            if (v1.size() == 2 && !v2.empty()){
                ans = max(ans, v1.back() + v1[v1.size() - 2] + a[u] + v2.back());
            }
            if (v1.size() == 1 && !v2.empty()){
                dp[u] = max(dp[u], a[u] + v1.back() + v2.back());
                ans = max(ans, v1.back() + v2.back());
            }
        };

        dfs(dfs, 1, -1);
        cout << ans << '\n';
    }

}