# codeforces-editorials

### 1054F

对这种在两个状态间进行变换，且操作可逆的构造，可以考虑统一变换到一个更简单的中间状态。例如将所有 0 和 1 分离，存储在两个不同位置。

步数限制为 4s，因此每轮限制为 2s。即每个字符必须在两步以内到达集中点。构造方法很多，可以从 $2\times 2$ 的情形开始考虑。

### 958C3

????

### 1184E3

E1/2/3 依次加强。E2 提示根据是否在 MST 上分成两类考虑。每条不在 MST 上的边都对应树上的一条路径，它至少要与路径中的最大边相同才能属于某棵 MST。对于在 MST 上的边，考虑所有经过它的路径所对应的树外边边集，它不能大于这个边集中的任意边。

前半个问题可以用倍增 LCA 解决。后半个问题有很多两个 log 的做法。可以用并查集做到一个 log。因为要取经过边的路径的最小值，从小到大处理路径，这样一条边被赋值就不会再变化，可以用并查集将这条边中的儿子合并到父亲。

$O((m+n)logn)$。

### 873E

枚举 3 个分割点复杂度过高，考虑直接算出最佳的第 3 个分割点。首先根据前两组的长度计算出第 3 组的合法长度范围，然后取相邻项差值最大的位置。后者可以做到 $O(n^2)-O(1)$。（还可以 $O(n^{1.5})-O(2)$ 以及 $O(n)-O(1)$，但比较麻烦）

$O(n^2)$。

### 1107E*

最后一次删除的串是原序列的一个子序列，该子序列之外的段都是子问题。根据是否属于子序列想到两种转移，一种是将某个字符加入子序列，另一种是将一个段视为子问题。因为要加上最后删除串所得的分数，状态需要记录子序列的长度。可以枚举保留 0 还是 1，然后用 $f(i,j)$ 表示处理了前缀 $i$，子序列长为 $j$，当前累计的最大分数。这样我们就可以在所有子问题都解决的前提下，$O(n^3)$ 得到答案。整体的复杂度是 $O(n^5)$，还需要优化。注意到我们在计算子问题 $[l, r]$ 时其实也得出了 $[l, r-1]$ 所需的状态，可以将 $[l, l..n]$ 这组子问题一起计算，复杂度降为 $O(n^4)$。

tips：对于删除串的问题，可以通过考虑最后一步来观察区间所对应的子问题之间的转移。本题中这一转移比较复杂，需要通过另一个 DP 来完成。

### 1061F*

要获得关于路径的完整信息，首先需要花费 n-2 次询问得到路径上的点。一个简单的想法是随机 60 条路径求交，将出现次数最多的视为根。没算过概率，只是感觉有点低。于是考虑精确定位路径上的根（假如有的话）。

首先要判断根是否在路径上。路径外的点可以分为三种，连接到两个端点的，以及连接到路径上其他点的。通过询问 (i,u,v) 和 (u,v,i) 可以得到连接在两个端点上的子树的大小。如果其中一棵子树的大小恰为 $(n-1)/k*(k-1)+1$（根加上根的 $k-1$ 个儿子），那么它就是根。如果大小超过了这个值，则说明根也在这颗子树中，这条路径不经过根。否则 $u$ 和 $v$ 应该没有祖先关系，可以直接从子树大小得到它们的深度。根据深度和路径的长度就能判断 LCA 的位置，从而判断是否跨根。如果跨根，那么可以通过询问 (u,i,j) 来比较路径上点到 $u$ 的距离，对它们排序，从而找出根。

### 961G

有点纸老虎的感觉。

答案除以所有数字之和后，就是特定的一个数字 $x$ 在所有方案中所处集合大小的和。一个思路是枚举它所在集合的大小并计算出现次数，但出来的式子不会算。

注意到每个数字的每次出现至少会贡献 1，也就是总的方案数 $S(n,k)$。在样例中减去这一部分后剩下的值好像可以被 $n-1$ 整除。进一步思考后发现可以将所有方案的构造分成两种，类似于第二类斯特林数的递推公式。

1. $x$ 所在集合只有 1 个元素。$S(n-1,k-1)$。
2. 可以视为 $x$ 选择 $k$ 个已有集合之一加入。方案数贡献是 $S(n-1,k)\cdot k$。因为这些集合大小始终为 $n-1$，集合大小贡献是 $S(n-1,k)\cdot (n-1)$。

等价于 $S(n,k-1)+S(n-1,k)\cdot (n-1)$。因此算两个第二类斯特林数即可。我只会 $O(klogn)$。