CF2229 (Codeforces Round 1100, Div. 1 + Div. 2) 补题笔记

JuRuoOIer · 2026-05-24 08:03:07 · 个人记录

Codeforces Round 1100

完蛋感冒了，这么晚才写完，谢罪。

前情提要：本场 EFGHI 题均为 DP。

upd log：

• 2/6/2026：修了 typo，“好客的”是 hospitable。感谢审核员指出。
• 2/6/2026：补了 D 题特别牛的做法！
• 31/5/2026：根据@沉石鱼惊旋 大佬的建议，修改了 H 题的一点细节。以及 HI 我没有太多自己的东西，就不打算交题解区了。
• 27/5/2026：C 的数据范围漏了个 \sum。由于问题不大，C1/C2 的题解区不重新交了。

A

自评：红。

简要题意

给定长度为 n 的数组 a，每次操作可以选一个 x，然后对于所有 a_i 使其增加 \text{sgn}(x-a_i)，求使所有 a_i 都相同的最小操作次数。

数据范围：多测，t\le 100,n,a_i\le 10^3。

做法

显然选多个 x 是不优的，因为这唯一的影响是可能导致某些数浪费两次操作。

对于同一个 x 答案就是和它相差最大的那个差，于是联系初中学习的数轴相关知识（其实原题面甚至已经帮你联系了）得知选最大和最小值的中点最优，即答案为 \lceil\frac{mx-mn}{2}\rceil（其中 mx 是最大值，mn 是最小值）。

单组复杂度 O(n)。

B

自评：橙。

简要题意

给定长度为 n 的数组 a,b，对于每个 i，你可以（不必须）交换 a_i,b_i，求操作后 \displaystyle\max_{i=1}^n\{a_i\}+\sum_{j=1}^nb_j 的最大值。

数据范围：多测，t\le 10^4,\sum n\le 10^5。

做法

既然 a 中只能贡献一个，我们先尽可能让大的贡献，即让 a_i\le b_i。为了方便，以下不妨直接设 a_i\le b_i。这样刚才方案的答案就是 \displaystyle\max_{i=1}^n\{a_i\}+\sum_{j=1}^nb_j。

由于 a 只能贡献一个，所以换多个则一定有些位置是纯亏的，所以只需要考虑换一个的情况，设交换了 a_x,b_x。一种可能是 a 的最大值没变，这种情况同样是纯亏的；否则有 b_x>\max\{a_i\}\ge a_x，则 b_x 顶掉了原来 \max\{a_i\} 的贡献，a_x 顶掉了原来 b_x 的贡献，算下来就是 a_x 顶了 \max\{a_i\} 的贡献，而 a_x\le \max\{a_i\}，故还是不优的。

综上，操作后的 a_i' 取 a_i,b_i 的较小值最优。

单组复杂度 O(n)。

C

自评：红（C1）橙（C2）。

简要题意

给定长为 n 的非零数组 a，你可以进行不超过 n 次操作，每次可以选一个正数 a_i，并将 a_1 至 a_i 全部取相反数。求构造一种方案，使得操作后 \sum a_i 最小（C1）/ 最大（C2）。

数据范围：多测，t\le 10^4,\sum n\le 2\times 10^5。

做法

首先 C1 可以倒序操作每个正数（注意后面操作对前面是有影响的，这里正数指的是当前状态下的正数而非原始数组中的正数）然后就全变成负的了。

然后 C2 延续 C1 的思路，可以选恰好一个正数（显然选多个是浪费操作）并以将它变成负的为代价，把它之前的全变成正的。通过计算前缀和及前缀绝对值和可以求出若选择该正数答案是多少，取最大的并延续 C1 的构造方法即可，只不过最后要记得操作一次选定的值。

单组复杂度 O(n)。

D

自评：绿。

前情提要：这里有非常逆天的做法，建议看看。

简要题意

给定长度为 n 的数组 a,b，每次操作可以选择一个 i，并将 a_i,a_{i+1} 替换为一个 a_i,a_{i+1},b_i,b_{i+1} 中的第二小，b_i,b_{i+1} 替换为一个 a_i,a_{i+1},b_i,b_{i+1} 中的第三小。这样重复 n-1 次，a 和 b 中就都只剩下一个元素了，求这两个元素的最小值最大可以是多少。

数据范围：多测，t\le 10^4,\sum n\le 10^5。

做法一

高一补过十来场 CF，这个想法在这之间好像也不是第一次出现了，可以当个模型记忆。

求最小值最大且有单调性，考虑二分答案。check 时将 <mid 的数变为 0，\ge mid 的数变为 1，如果最终能剩下 1 就返回 true。

在本题中 a_i,b_i 的“地位”是相同的，故每个 i 上只有三种情况：(0,0)、(0,1) 和 (1,1)。(0,1) 和别的合并时，别的不受影响，故可以忽略 (0,1)。然后应该是 (1,1) 和 (0,0) 合成 (0,1)，最后只要能剩下 (1,1) 就算成功。于是为了省一些 (1,1) 我们发现 (0,0) 和 (0,0) 合成完还是 (0,0)，即忽略 (0,1) 后连续的 (0,0) 可以视为一个。这样算下来 (0,0) 的个数能严格小于 (1,1) 的个数就可以留下 1 了。

check 是 O(n) 的，故单组复杂度是 O(n\log n) 的。

做法二

Solution from @akane646, proof by myself.

断言 每次取 s_2+s_3 最小的对一定最优。

::::info[证明]{open}

由于这里操作的过程是一个类似链表删除的结构，所以直接像本场 B 题或 F 题那样直接交换来证是不太容易的。所以我们先考虑容易交换的情况，即 n=3。

此时我还是不太会证。但是我们是 OIer，所以我们可以花五分钟央求我们温柔美丽可爱强大的 C++ 姐姐帮我们证：

:::success[Code]{open}

//Please ignore those headfiles.I write them just because
//DEV-C++ won't support completion if i use <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cctype>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<queue>
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
#define LL __int128
#define ui unsigned int
using namespace std;
ll a[]={1,2,3,4,5,6};
ll sec(vector<ll> tmp){
    sort(tmp.begin(),tmp.end());
    return tmp[1];
}
ll thi(vector<ll> tmp){
    sort(tmp.begin(),tmp.end());
    return tmp[2];
}
int main(){
    ios::sync_with_stdio(0);
    for(int i=0;i<720;i++){
        ll l=thi({sec({a[0],a[1],a[2],a[3]}),thi({a[0],a[1],a[2],a[3]}),a[4],a[5]}),r=thi({sec({a[4],a[5],a[2],a[3]}),thi({a[4],a[5],a[2],a[3]}),a[0],a[1]});
        if(l==r){
            continue;
        }
        if(!((l<r)^(sec({a[0],a[1],a[2],a[3]})+thi({a[0],a[1],a[2],a[3]})<=sec({a[4],a[5],a[2],a[3]})+thi({a[4],a[5],a[2],a[3]})))){
            for(int j=0;j<6;j++){
                cout<<a[j]<<' ';
            }
        }
        next_permutation(a,a+6);
    }
    return 0;
}

:::

她什么也没说，看来是默许了，于是在 n=3 时以上结论成立。

于是对于 n>3，对于不符合我们条件的方案，我们可以利用以上证明进行邻项交换，将其变为符合我们条件的方案。

::::

维护当前每个位置的前一个和后一个，并使用 multiset 维护各对 (i,i+1) 的 s_2+s_3 即可做到 O(n\log n)。

E

自评：下位蓝。

简要题意

给定 n 个点的无根树。你有一个初始为空的集合 s，并将要进行 n-1 次以下操作：将编号最大的叶子的编号加入 s，并任选另外一个叶子将其删除。求最终得到的 s 可能有多少种，对 998244353 取模。

数据范围：多测，t\le 10^4,\sum n\le 2\times 10^5。

做法

以下“u 的子树”不含 u 本身，原因您看完就懂了。

考虑一个非叶子 u 什么时候能变成叶子。

若将其视为根，则显然是其除某一个儿子及其后代以外所有后代都被删除后。而这个过程中被删掉的点都会有一段时间变成叶子。

于是问题在于，如果某个点变成叶子时刚好变成了当时最大的叶子，那该点不能直接删，只能先把一个更大的变成叶子再删。这样一来，这个“更大的”就也要被加入 s 中。

因此 u 首先得大于 u 除某一个儿子及其后代以外所有后代的最大值才可能被加入 s。由于 u\neq n 时一定存在一个儿子满足其或者其子树内包含 n，故除去的那个儿子只能是该儿子，于是为了方便我们直接将 n 作为根（并特判掉 n 本身就是叶子的情况），这样删的范围就是 u 的子树。

而在将 u 加入 s 的过程中，如果其子树中存在可能成为最大叶子的点，设这些点中最大的为 v（显然，根据可能成为最大叶子的点的条件，它一定也是 u 子树内的最大值），那我们总是需要在编号区间 (v,u) 内找一个点加入 s 以确保 v 能被顺利删除，无论我们是否真的将 v 加入了 s——反之，u 将不能被加入 s，因为为了删除 v，一定要选一个 (v,n] 的点，若不选 (v,u) 内的点，则只能选 (u,n] 内的点了。

于是我们得到了一个思路：设 dp_i 表示只考虑 [1,i] 内的点，且将 i 加入 s 的方案数。设 j 为 i 子树内的最大值，则转移为 dp_i=\displaystyle\sum_{k=j+1}^{i-1}dp_k。这是个区间求和，故可以用前缀和优化做到 O(n)。

好心的出题人在最后一组样例中提醒了您只是这样并不够，因为有些点（该样例中的 2,3）即使满足条件也不可能先于 n 被删除。所以 n 的转移应该是所有不可能先于 n 被删除的 dp 值之和。这要求计入答案的点大于 n 的子树中，除了包含该点的儿子及其子树外所有点的编号。因此，这些点一定在 n 的儿子中，子树内包含 n-1（或者其本身即为 n-1）的那个儿子及其子树内。求出 n 子树内其他点的最大值并遍历这个儿子的子树即可得到答案。

单组复杂度 O(n)。

F

自评：下位紫\~中位紫。（好像评高了？）

在本文中，你将看到评论区中的多种做法，包括几乎稳过的随机化做法。

简要题意

给定长度为 n 的数组 a。你有一个长度为 k、初始全为 0 的数组 b。你可以将 a 中的元素任意排序，然后按你所排的顺序，将每个 a_i 加到当前 b 中任一最小值上。求操作后 b 中最大值最大可以是多少。

数据范围：多测，t\le 10^4,n\le 18,\sum 2^n\le 2^{18}。

做法〇

Solution from @RockyYue.

这位大佬暴搜剪枝获得了 62 ms 的好成绩，感兴趣的可以看看，写在这里仅作膜拜用。

做法一

The same solution as the official editoral.