CF Round 1023 (Div. 2) 补题

Codeforces Round 1023 (Div. 2) 补题

此次排名情况：

• 共 8k+，排名 1651，做出 ABC 三题。
• Rating +81，当前为 1442。
• 比赛链接

A. LRC and VIP

题意：有一个长度为 n 的数组 a，你需要将数组分成 2 个序列，每个元素只能属于二者之一，每个序列至少包含一个元素，两个序列全部 GCD 不相等。

题解：当数组 a 中的元素全部相等时，不论序列如何分，两序列 gcd 相等，不可能划分。比较最大值和最小值，如果相等输出 NO。否则将最大值一个元素作为序列，其余的作为另一个序列即可。

void solve(){
    int n;cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int mn=*min_element(a.begin(),a.end());
    int mx=*max_element(a.begin(),a.end());
    if(mn==mx){cout<<"No\n";return;}
    cout<<"Yes\n";
    for(int i=0;i<n;i++)
        cout<<(1+(a[i]==mx))<<"\n";
}

B. Apples in Boxes

题意：有一个长度为 n 的数组 a，两个人轮流操作。选择一个大于 0 的元素减 1。如果操作后 max(a)-min(a) > k，当前人输。

题解：假设 max-min ≤ k 成立且至少有一个 \(a_i≥1\)。从最大元素中减去不会使条件变差。唯一输的方式是将所有 \(a_i\) 全部减到 0，执行 sum 次操作后全部输掉。

C. Maximum Subarray Sum

题意：给你一个长度为 n 的数组 a 和一个正整数 k，数组中有些元素可以任意更改，使最大子数组和正好是 k。

题解：将可替换元素全部改为 -INF，如果最大子数组和仍然大于 k，不可能。选某个可替换元素，计算前面和后面的最大子数组和，然后将这个元素更改为使总和为 k 的值。

D. Apple Tree Traversing

题意：有一棵 n 个节点的树，每个节点上有一个苹果。选择一条每个节点上都有苹果的路径 (u,v)，写下 (d,u,v) 后去掉路径上所有的苹果。使写下的序列最大。

题解：一棵树中的最长路径为树的直径。假设 \(f_i,g_i\) 是 i 的子树中从 i 出发的最长和第二长路径，则树的直径为 \(max_{i=1}^n f_i+g_i\)。使用 set 和 priority_queue 维护，复杂度 \(O(n log n)\)。