Codeforces 3400 题目乱刷

注意

题解写的可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

CF1010F Tree

2024-04-21

题意

给定一棵 $n$ 个点的有根树，保证每个节点有不超过两个儿子。你要首先选出一个包含根的连通块，然后给每个选中的点填一个非负整数，使得每个节点的数大于等于其子节点的数之和。根节点的数给定为 $k$。求方案数。$n\leq 10^5, k\leq 10^18$，7s。

题解

Tags:

• 多项式
• 生成函数
• 半在线卷积

设 $f_i(x)$ 为生成函数，考虑 $i$ 为根的子树，$x$ 的指数对应节点 $i$ 上的数。设 $l,r$ 分别为 $i$ 的左右儿子，有：

$$f_i=1+f_l \cdot f_r \cdot \frac{1}{1-x}$$

设 $z=\frac{1}{1-x}$，考虑如何求出 $f_i$ 写成 $z$ 的多项式后的结果。

一个自然的想法是，每个点的状态由重儿子继承上来，再用轻儿子大小的复杂度合并上轻儿子的状态。但多项式乘法没办法做 $O(\min(n,m))$。

我们考虑将 $f_i$ 用一列多项式 $a_{i,1}, \dots, a_{i,m}$ 表示，要求 $f_i = (((a_{i,1}+1)a_{i_2}+1)\dots +1)a_{i,m}+1$。用 $a_{i, \cdot}$ 求 $f_i$，只需要 $O(n \log^2 n)$ 的时间做半在线卷积即可；而转移方程可以写成 $f_i = (f_l) \cdot (z f_r) +1$ 的形式，即只需要在列表末尾添加 $z f_r$。总复杂度为 $O(n \log^3 n)$。

求出 $f_1(z)$ 后，要求 $[x^k] f_1 = \sum_i [x^k] (\frac{1}{1-x})^i Z_i$，只需求若干组合数即可。

CF1098E Fedya the Potter

2024-04-21

题意

给出序列 $a_{1 \dots n}$，将 $a$ 的所有区间 $\gcd$（共 $n+1\choose 2$ 个）排序得到序列 $b$，将 $b$ 的所有区间和排序得到序列 $c$，求 $c$ 的中位数。$n\leq 5\times 10^4, a_i\leq 10^5$。

题解

Tags:

• 最大公约数
• 倍增
• 类欧几里得算法

首先考虑序列 $b$ 的形式。在固定 $a$ 的子区间的左端点后，随着右端点的变化，$\gcd$ 至多变化 $\log a_i$ 次，变化点可以倍增找到。因此我们可以得到至多 $n \log a_i$ 个不同的 $\gcd$，因此序列 $b$ 的形式即为若干个值一致的连续段，不妨设 $b$ 中有 $m$ 个不同的数。

现在考虑第二部分。二分中位数 $c$，此时我们需要求 $\leq c$ 的区间和的数量；抛开 $r>l-1$ 的限制，把所有 $(s[l], s[r])$ 放在平面上，我们需要查询 $y-x=c$ 下方的点的数量。这些点可以被分成 $m^2$ 的矩形区域，每个区域内都是以一定间隔均匀分布的；对于被直线切割到的矩形区域，我们需要用类欧几里得算法求点的数量；对于没被直线切割到的矩形区域，直接累加即可区域内的点即可。

CF1012F Passports

2024-04-22

题意

你有 $P$ 本护照，有 $n$ 个国家的旅游计划。每个国家你会在第 $s_i$ 天清晨到达，在第 $s_i+l_i-1$ 天离开，这个国家的签证需要 $t_i$ 天来办理。

• 你每到达一个国家时，你需要保证你带着的护照中有至少一个护照有这个国家的签证。
• 如果你第 $x$ 天在起点，那你可以在当天中午把护照交给使领馆，第 $x+t_i$ 天中午无论你是否在起点都可以拿回护照（如果你在起点，你可以随即办理下一个国家的签证）。

问能否完成旅游计划。$P\leq 2$，$n\leq 22$，$s_i,l_i,t_i\leq 10^9$。

题解

Tags:

• 状压 DP

先将国家按照到达时间排序。

护照和签证的限制整理后如下：

• 开始办签证时，你必须在起点（没有旅游计划）。
• 签证的办理时间早于到达时间。
• 考虑一个护照，其每个签证的办理时间都不应与护照上的国家的旅游计划重叠。

状压 DP，设 $f[S]$ 表示办理完 $S$ 集合内所有签证，最早拿回护照的时间。转移时枚举下一个国家，我们需要找到一个尽可能早的开始办理签证的时间：

• 首先开始时间不能在旅游计划内。
• 办理签证的总时段所相交的旅游计划集合，不能与 $S$ 有交。

我们从拿到签证的时间开始枚举，如果当前开始时间不合法，我们直接跳到下一次某个旅游计划结束的时间，再检查，直到找到一个合法的开始时间（或者找不到）。然后检查这个开始时间是否在对应旅游计划之前。

与开始时间和结束时间相关联的旅游计划可以双指针维护，同时也记到状态里，这样复杂度就（大概）是 $O(2^n n)$ 的了（心虚）。

对于 $P=1$ 的情况即考察 $f[\{0,1,\dots,n-1\}]$ 即可，对于 $P=2$ 的情况找到 $f[S]$ 和 $f[\{0,1,\dots,n-1\}\setminus S]$ 都合法的 $S$ 即可。

CF1023G Pisces

2024-04-27

题意

一棵树，边有长度。树上有很多鱼（怪），鱼每天可以沿着边走一单位长度。有 $m$ 条信息，每一条形如在第 $d$ 天有至少 $f$ 条鱼在节点 $p$。求树上至少有多少鱼。$n,m\leq 10^5$。5s。

题解

Tags:

• 图论
• Dilworth 定理
• 最大独立集
• 数据结构优化 DP
• 均摊复杂度
• 启发式合并

对于每条信息，建 $f$ 个点，代表观察到 $f$ 条鱼。如果一个点能在相应时间内到达另一个点，则连一条有向边。从而问题转化为一个 DAG 的最小链覆盖。

最小链覆盖等于最长反链长度。不难发现选取了一个点在反链里，则把这个点所在的信息的所有点都选中肯定才优；同时本题的边是有传递性的，从而问题转化为：选取若干信息，其互相之间不能到达，使得被选出的总鱼数最大。

DP，设 $f[i,l,r]$ 表示考虑点 $i$ 子树内的选法，不可能从选中的点到达在 $(l,r)$ 时段内的父亲、也不能从在 $(l,r)$ 时段内的父亲到达选中的点，选出来的节点的最大总价值。这个 DP 不太现实，但可以发现，我们可以把时段 $(l,r)$ 改成时刻 $t$，只要这个时刻 $t$ 不与选中点互通的即可。

我们会对 $f[i,t]$ 做几种操作：

• 合并两个 $f[i,t]$（对位相加）

• 扩展一个 $f[i,t]$ $k$ 的长度，得到 $f'[i,t] = \max_{t-k\leq j\leq t+k} f[i,j]$。

• 合并完子树的 $f$ 后，我们要把 $i$ 节点上的观察算进来。不妨记 $i$ 到父亲的边边权为 $l$。为此，我们有两种选择：不选择 $i$ 节点上的观察，这样得到 $f[i,t]$ 扩展 $l$ 的结果；或者选择 $i$ 节点上的观察，得到 $f'[i,d+j] \gets f[i,d]+f, |j|<l$。

  这个操作相当于我们将 $f$ 扩展 $1$ 得到 $f'$，然后将【$f$ 单点加 $i$ 处各观察】和 $f'$ 取 $\max$，然后将 $f$ 扩展 $l-1$。

我们使用数据结构维护差分数组。对于为正和为负的元素分别开两个 map 维护：

• 合并操作直接启发式合并
• 扩展操作会使得所有正元素左移、负元素右移，为此要打 tag。移动过程可能使得一个 ↓↑ 式的区间消失、两个元素合并为一个；为此我们维护一个优先队列，记录所有 ↓↑ 式的区间的（tag 为 $0$ 时的）长度，当这个长度小于等于二倍 tag 时，这个区间就会消失.
• 对于第三套操作，$f$ 扩展 $1$ 得到 $f'$ 会使得某些位置增加，对 $f$ 单点加也会使得某些位置增加。我们对于所有要做单点加的地方，求这些位置通过扩展 $1$ 会增加多少；扩展 $1$ 后，我们再对这些位置单点加上【$\max(0, \text{单点加产生的增量}-\text{扩展 1 产生的增量})$】。

时间复杂度 $O(n\log^2 n)$（假装 $n,k$ 同阶）。

CF1039E Summer Oenothera Exhibition

2024-04-29

上来就分块，结果就只想出来 $O(n^{5/3} \log n)$ 空间复杂度还爆炸的做法，寄。

题意

给定长度为 $n$ 的序列，常数 $w$，询问次数 $q$。接下来 $q$ 组询问，每次给出一个常数 $k_i$，求最少把序列分为多少段使得每段序列中数的极差不超过 $w-k_i$，输出最小的段数。$n,q\leq 10^5, w\leq 10^9$。

题解

Tags:

• 根号分治
• LCT
• ST 表

首先可以发现，当 $w-k_i$ 确定之后，可以每一段贪心尽可能地长。我们对每个点向后连边，连到自其开始、最长的极差不超过 $w-k_i$ 的区间的右端点的下一个点，由此得到一棵树。答案即为 $1$ 的深度（减个常数）。

设定一个常数 $B$，我们用数据结构维护 $\leq B$ 的跳跃，而 $>B$ 的跳跃我们使用 ST 表来找。

将询问离线，按允许极差从小到大排序；提前预处理出来每个点能跳到的最远点的前 $B$ 个变化时刻。这样我们要做的操作为：

• 更改一个点的父亲（也有可能直接断掉其与父亲的边）
• 查询一个点所在子树的根，以及这个点的深度

查询时，先处理更新，然后从这个点开始，不断跳到根、然后用 ST 表跳一步，直到跳到 $n+1$。

考虑如何实现数据结构的部分。这部分类似于“弹飞绵羊”一题，官方题解选择分块维护，最后复杂度为 $O(n^{5/3})$，而大部分洛谷上的题解选择 LCT，复杂度为 $O(n^{3/2} \log n)$。

由于 LCT 远慢于 ST 表，这个 $B$ 实际上要取到比 $\sqrt n$ 小上几倍。