Problems（2026/01）

· · 个人记录

back。

\color{orange}\blacksquare P5397 [Ynoi2018] 天降之物 \dagger, \blacktriangle

:::warning[仍在施工]

哎哎，神秘诡异根分。

怎么回事，我不会的第四分块怎么成正解了不能这样啊【拔刀】。

题目大意：修改将所有 x 替换成 y，查询最小的 x 与 y 的距离。

要是你放过 \mathcal{O}(n \sqrt{n \log n}) 我就会了啊呜呜呜。

先考虑静态的情况。对于 x,y 的出现次数 c 分治，设分治阈值为 b（不过肯定是 b = \sqrt{n} 的复杂度要平衡），令 c_x \le c_y。

考虑动态。 ::: ### $\color{purple}\blacksquare$ P5309 [Ynoi2011] 初始化 > 题目大意：修改，所有 $i \bmod x = y$ 的位置的 $a_i$ 全加上 $z$；查询，区间和。 这种 $i \bmod x = y$ 的即剩余系平衡，考虑平衡规划，设阈值为 $b$。先看修改。 - 若 $x \gt b$，则满足条件的 $i$ 有 $\mathcal{O}\left(\frac{n}{b}\right)$ 个，直接暴力改。时间复杂度 $\mathcal{O}\left(\frac{n}{b} \times p\right)$。 - 若 $x \le b$，需要更优秀的算法。我们发现它的优势是这样的 $x$ 只有 $b$ 种。不妨打表将计算过程放到询问里，记 $t_{x, y}$ 为对 $i \bmod x = y$ 的修改的 $z$ 值和。不过为了更快，记 $s_{x, y}$ 为 $t_{x, y}$ 的前缀和进行查询。时间复杂度 $\mathcal{O}(q + b)$。 其中 $p,q$ 是我们选用的一种数据结构的单修与区查的时间复杂度。 我们发现，在 $p = 1, q \le \sqrt{n}, b = \sqrt{n}$ 时复杂度最为优秀，为 $\mathcal{O}(n \sqrt{n})$。 而这种数据结构显然是分块。需要大力卡常。 ### $\color{red}\blacksquare$ CF1194F Crossword Expert > 题目大意：共 $n$ 个游戏，$T$ 秒，每个游戏有 $1 / 2$ 的概率花 $t_i$ 秒，$1 / 2$ 的概率花 $t_i + 1$ 秒，求完成的游戏个数期望。 无赖做法。 记 $s$ 为 $a$ 的前缀和。 期望的定义式是 $E = \sum _ {i = 0} ^ {n} iP_i$，可以考虑将它转化成 $E = \sum _ {i = 0} ^ {n} S_i$，其中 $S_i = \sum _ {j = i} ^ {n} P_j$ 即 $P$ 的后缀和。 $S_i$ 的组合意义为完成游戏个数不少于 $i$ 个的概率。其中总方案数是前 $i$ 个游戏的决策种类数即 $2^i$。合法方案数即选择不超过 $T - s_{i}$ 个游戏多花费一秒。即 $\sum_{j = 0} ^ {T - s_{i}} \binom{i}{j}$，二者相除即可。 $$ E = \sum_{i = 0} ^ {n} \frac{\displaystyle\sum_{j = 0} ^ {T - s_{i}} \binom{i}{j}}{2 ^ {i}} $$ 观察发现这是一个下指标求和，不会推式子咋办。 可以直接离线后莫队暴力跑。时间复杂度 $\mathcal{O}(n \sqrt{n})$。 ### $\color{purple}\blacksquare$ CF1790F Timofey and Black-White Tree wyb 亲传的 $\mathcal{O}( n \ln n )$ 做法。 > 题目大意：每次染黑一个点，求染黑后的两点间最短距离。 我不会平衡规划。 有一个神秘结论，在染黑了 $x$ 点之后的最短距离是 $\mathcal{O}\left(\frac{n}{x}\right)$。不会证明。 考虑一种暴力，枚举 LCA。记 $d_{u}$ 为 $u$ 的子树内的黑点到 $u$ 的最短距离。 每次染黑一个点 $v$ 后，枚举 $v$ 的 $i$ 级祖先 $w$，将 $d_w + i$ 作为值更新答案 $\text{ans}$。正确性显然，时间复杂度 $\mathcal{O}(n ^ 2)$。 考虑优化，由于在染色之前已经有最优解 $\text{ans}$，故 $i$ 的上界是 $\text{ans}$ 而非 $n$。根据我们之前提到的结论，复杂度为 $\mathcal{O}\left( \sum \frac{n}{i} \right) = \mathcal{O}(n \ln n)$。 跑得飞快，只用了 187ms，比 wyb 的 250ms 还快，你也来试试吧！ ### $\color{red}\blacksquare$ CF1032F Vasya and Maximum Matching jzp 讲的喵喵 dp 题。 > 题目大意：对一棵树求删边方案个数使得删完存在唯一最大匹配。 我们容易发现对于一棵树进行删边形成的结构是一个森林，即多棵树。那么可以分析一下一棵树存在唯一最大匹配的条件。 手玩一下样例再构造几种树会发现，每一个结点在最大匹配中必须恰好被一条边选择，否则可以与相邻的点进行交换这样匹配数量就不唯一。 当然还有一种可能是孤立点，即没有边的树。 我们的 dp 方式有眉目了，考虑记 $f_{u, 0/1/2}$ 为 $u$ 是单点 / 与儿子连边 / 与父亲连边时子树内部的删点方案数。 $f_{u, 0}$ 的转移较为简单： $$f_{u, 0} = \prod _ {v \in g_u} (f_{v, 1} + f_{v, 0})$$ $f_{u, 2}$ 次之，对于所有 $v$ 进行决策，若 $v$ 是孤立点则该边必须删掉，否则可删可不删，故 $f_{v, 1}$ 项要带一个 $2$ 的系数： $$f_{u, 2} = \prod _ {v \in g_u} (2 \cdot f_{v, 1} + f_{v, 0})$$ $f_{u, 1}$ 则是枚举向父亲连边的 $v$，除 $v$ 外剩余转移与 $f_{u, 2}$ 同理： $$f_{u, 1} = \sum _ {v \in g_u} f_{v, 2} \times \prod_{w \ne v} (2 \cdot f_{w, 1} + f_{w, 0})$$ 显然这个式子可以转化成全局积除以单点值，模数为质数，正确。 ### $\color{red}\blacksquare$ CF1819C The Fox and the Complete Tree Traversal > 题目大意：一棵树上每个点可以跳到离该点距离不超过 $2$ 的位置，问是否能不重不漏地跳完整棵树。 有一个神秘结论，这棵树可以跳完当且仅当这棵树的形态是一个链上挂着若干个单点。如何证明？ > **充分性**；即举出一种构造方法。可以考虑从左往右遍历链，奇数位置取该点，偶数位置取该点连向的所有边，然后再反着取一遍。可以证明每次取的两个点的距离不超过 $2$。 > > **必要性**；反证法，假设有一个点 $v$ 挂了一个并不是单点的子树，而其在链上的前一个点为 $u$，后一个点为 $v$。在第一次的遍历中要么从 $u$ 来要么从 $v$ 来，此时必会存在两个相邻的链上点被同一次遍历选到，故第二次遍历将会失败。无法成功故不存在这样的合法树。 事实上这个链挂单点的结构中的链一定是直径。所以说只需要写一个双 dfs 求直径即可。 ### $\color{red}\blacksquare$ CF1868C Travel Plan > 题目大意：一个 $n$ 个点的完全二叉树，求在所有点权值不超过 $m$ 的情况下，$\sum_{s} \sum_{t} d_{s, t}$ 的值，其中 $d_{s, t}$ 为路径最大值。$n \le 10^{18}, m \le 10^5

发现 m 较小，考虑枚举 d_{s, t} = k，则对于每一种 k 求出 \sum_{s}\sum_{t}[d_{s, t} = k] 即可。我们发现这个式子并不好求。但它的前缀和式子 \sum_{s}\sum_{t}[d_{s, t} \le k] 好求。即路径上所有点的点权都不大于 k 的路径个数。

路径个数可以枚举 lca 然后在 lca 处统计 dp。因为是完全二叉树所以任何子树大小相同的点子树形态也就相同，直接枚举子树大小即可。而子树大小至多有 \log n 种。

路径有关 dp，直接插头；记 f_{u, k} 为 u 子树内的路径，g_{u, k} 为 u 子树内到 u 的路径个数。

然后转移做完了 qwq。复杂度 \mathcal{O}(Tm\log n)

\color{red} \blacksquare CF1859E Maximum Monogonosity

题目大意：给两个长为 n 的序列 a, b，选择若涵个总长为 k 的区间，使得 \sum |b_l - a_r| + |a_l - b_r| 最大。n, k \le 3 \times 10^3

这种绝对值题不要想着去预处理贡献然后做，这种题很多都是拆绝对值做，本题也不例外。

考虑一种朴素 dp，记 f_{i, j} 为前 i 位中已经选取了总长位 j 的若干区间后的最大价值。

f_{i, j} = \max\left( f_{i - 1, j}, \max_{h = 1} ^ {j}f_{i - h, j - h} + |b_{i - h + 1} - a_i| + |a_{i - h + 1} - b_i| \right)

复杂度是 \mathcal{O}(n^2k)，不可过。考虑拆绝对值优化。

一个形如 |x| + |y| 的绝对值式子可以转化成 \max(x + y, x - y, -x + y, -x - y)，本题同理。而最终求的是最大值也就是说除最大值外三个是否参与计算事实上不重要。

\begin{align*} |b_i - a_j| + |b_j - a_i| &= \max\{(b_i - a_j + b_j - a_i, b_i - a_j - b_j + a_i, -b_i + a_j + b_j - a_i, -b_i + a_j - b_j + a_i\} \\ &= \max\{(b_i - a_i) + (b_j - a_j), (b_i + a_i) + (-b_j - a_i), (-b_i - a_i) + (b_j + a_j), (-b_i + a_i) + (-b_j + a_j)\} \end{align*}

这个可以直接拆成四种贡献并分开计算，记一个前缀 dp 值最大值即可，时间复杂度 \mathcal{O}(nk)，可过。