educational round 1796 D & E 解题报告

Part1

D

【题意】

有一个数组 \(\{a_n\}\)，给定 \(x,k\)，现在要将数组内 \(k\) 个数加上 \(x\)，其他的数减去 \(x\)。问得到的所有可能数组中最大子段和的最大值。

\(1 \le n \le 2 \times 10^5, 0 \le k \le \min(20, n), -10^9 \le x, a_i \le 10^9\)

【分析】
场上看到了 \(20\)，感觉是个很关键的性质，想到先给所有数减去 \(x\)，然后只有 \(20\) 个位置变动。然后由于最大子段和是 dp，我也就往 dp 上顺着想。于是就想出来了。但是思路不够清晰，调了很久。

令 \(dp_{i, j}\) 表示用了 \(i\) 个 \(2x\)，\([1, j]\) 最大后缀和。
我们的 dp 转移：
\(dp_{i, j} = \max(dp_{i-1, j - 1}+a_i + 2x, dp_{i, j-1} +a_i, 0)\)

最后的答案就是 \(\max \limits_{i = 1} ^ n \max \limits_{j = \max(0, k - n + i)} ^ k dp_{i, j}\)。

注意边界，对于 \(i < j\) 的位置不合法。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e18;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
//调不出来给我对拍！
int dp[200100][30], tr[200100][30], tmp[200100][30];
int a[200100];int n,k,x;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int T; cin >> T;
    while(T--) {
        cin>>n>>k>>x;
        f(i,0,n)f(j,0,25)dp[i][j]=0;
        f(i,0,n)f(j,i+1,25)dp[i][j]=-inf;
        f(i,1,n){cin>>a[i]; a[i]-=x;}
        x=x+x;
        int ans=0;
        f(j,0,k){
            f(i,max(1ll, j),n){
                cmax(dp[i][j], max({dp[i-1][j] + a[i], (j-1>=0?dp[i-1][j-1] + a[i] + x:0ll), 0ll}));
                if(n - i + j >= k) cmax(ans, dp[i][j]);            
            }
        }
        cout<<ans<<endl;
    }
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}
/*
2023/x/xx
start thinking at h:mm


start coding at h:mm
finish debugging at h:mm
*/

E

【题意】
给定一棵 \(n\) 点树，可以选定一个根，然后在上面选出一些深度不相同的点组成的链，这种方案的权值为这里面最短链的长度。求所有方案中，最大权值。

\(n \le 2 \times 10^5\)

【分析】
首先，这个剖分方式是“短链剖分”，而且是只能剖成不拐弯的链。但是我们二分答案可以有更好的判定。先考虑定下根了的情况。这种情况下，令 \(dp_i\) 表示该节点还需要往上加上多少个点才能达到长度要求。显然 \(dp_i = \max \limits_{j \in son_i} dp_j - 1\)。并且如果有两个节点的 \(dp\) 值都 \(>0\)，这个根一定不可行。

考虑这种情况下可能可行的根其实是有限的。如果这个有两个不好的子节点的点不是根，那么只有这两个不好子节点末端可能是根，其他情况下这个点依然存在两个不好的子节点或者不优（很好证明，但是证明的时候可以发现是根的情况会有所不同）。如果是根也好办，当没有其他节点满足存在两个不好子节点的时候，从一个不好子节点出发，一定能将两个节点“展平”，而这是能做到的最好效果（体会一下，如果有其他不好的，选其他的可能修复该节点和根；如果没有，最多是修复根）。

另外一种情况是 \(dp_1 > 0\)。这时候只有使用 \(1\) 的最短链（肯定是它导致的）做根是最好的选择。

注意特殊情况判断。

Part2

D 有和 \(k\) 无关的贪心做法，E 有不用二分答案的线性的 dp 做法。