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$ 小上几倍。

CF1045F Shady Lady

2024-05-19

题意

有一个系数待定的 $n$ 次二元多项式 $\sum_i ? x^{a_i} y_{b_i}$。甲先删去其中至多一项，然后乙填写正整数的系数。甲希望这个多项式可以取到 $-\infty$，而乙希望它有下界。求谁必胜。$n\leq 2\times 10^5$。

题解

首先考虑一个多项式什么时候有下界。首先添加一个常数项不影响答案。显然，如果单只有平方项（两个指数都是偶数的项）一定有下界，而非平方项则需要依靠不等式来保证大于等于已有的平方项的某个线性组合。

结论是：将每一项看作平面上的一个点，并额外带上 $(0,0)$；对所有点求（严格）凸包，若顶点有奇数点（任意一维是奇数），则无下界；否则有下界。感性理解的话，如果每个奇数点 $(a_0,b_0)$ 都能被其他偶数点非负地线性组合出来 $\sum c_i (a_i,b_i)$，则 $x^{a_i} y^{b_i}$ 可以看作平方项的加权几何平均，而几何平均是能被代数平均（一定非负）限制住的。

有了这个结论之后，问题转化为：甲能否去掉至多一个点（不能删去 $(0,0)$），使得凸包的顶点包含奇数点。一个做法是：先求出点集的非严格凸包，然后对凸包上的点依次染为红色、蓝色，$(0,0)$ 不染。对 点集-红色点集 和 点集-蓝色点集 两组点求严格凸包，若有奇数点，则甲必胜，否则乙必胜。

时间复杂度 $O(n\log n)$。