「Summary」2022-06-29 做题记录

分治肯定不是分治，倍增也肯定不是倍增，但蔬菜一定是蔬菜，我也一定是蔬菜。。。

2022-06-29

$\mathbb{CF627D}$

link

真·不是换根 $DP$

这。
首先二分答案。
设 $dp_u$ 表示以 $u$ 为根的子树中，$dfs$ 序前 $k$ 个结点的权值最小值的最大值。

对于子节点 $v$ ，如果 $dp_v = siz_v$。那么这棵子树可以完全塞进 $u$ 中。直接 $dp_u = dp_u + dp_v$ 。如果 $dp_v < siz_v$ , 如果非要让它产生贡献。那么只能是以这棵子树开头或是结尾。在回溯时可以把 $dp_v$ 的最大值塞进 $dp_u$ ，那么维护 $dp_v < siz_v$ 情况中 $dp_v$ 的次大值和最大值，在更新答案时可以用在 $dp_u$ 上加上次大值更新。

然后可以获得 $\mathtt{Wrong \ Answer \ on \ test \ 25}$ 的好成绩。
问题在于选根选错了。应该以点权最小的点当根，避免 $\mathtt{waste}$。

$\mathbb{CF875E}$

link

我却也是愚者

正着写 $check$ ，挂了 $3$ 发。。。
问题在于，你不知道这两个人的移动顺序，而正向移动时，两个人的初始位置定了，必有先后顺序。后效性时明显的。
考虑倒推，首先二分答案为 $mid$, 对于 $a_i$ ，一定有一人在 $a_i$，则只要另外一个不动人的在 $[a_i-mid,a_i+mid]$ 即可。
若上一步已经在该区间内，那直接区间变成 $[a_i-mid,a_i+mid]$ , 如果不在该区间内，则区间变成 $[\max(l, a_i-mid), \min(r, a_i+mid)]$ 。
最后判断得到的区间是否包含 $s_1,s_2$ 其中一点。

$\mathbb{CF147B}$

link

被 nKessi 嘲讽成套路题。

看到了最小环，想到 $\mathtt{floyd}$ ，然后得到一个 $\Theta(n^4)$ 的做法。
具体而言，是说 $dp[t][i][j]$ 表示，恰好经过 $t$ 条边，从 $i$ 到 $j$ 的最长距离。
那么找到一个最小的 $t$ 使得存在 $dp[t][i][i] > 0$ ，则最小正环的长度为 $t$ 。
因为 $dp[t][i][j] = dp[t - 1][i][j] + dp[1][i][j]$ ，这玩意是有可加性的，考虑倍增 $floyd$ 。
那么 $\Theta(n^3 \log_2n)$ 的时间复杂度就能解决它。
然后写挂了 $3$ 发。。。

$\mathbb{CF1059E}$

link

再次确认我不会写倍增

一眼贪心。
题目给的树上的祖辈关系很死，令 $len_u$ 表示从 $u$ 往上最多能够在满足情况的条件下覆盖的点的个数，一个倍增就能解决。
然后倍增写挂了。。。瞪了一下午。。。
树形 $dp$ 部分运用人类本质贪心覆盖就行。

$\mathbb{CF1394C}$

link

哦，原来我不能输出空字符串。

首先知道操作与这个字符串长啥样无关，操作的本质是加或减上一个 $B,N,BN$ 。
抽出来，对于一个字符串有 $cnt_b$ 个 $B$, 有 $cnt_n$ 个 $N$, 把它转化到坐标系里作为一个点 $(cnt_b, cnt_n)$ ，那么两个字符串相似等价于两个字符串映射到坐标系里是同一个点 $(cnt_b, cnt_n)$ ，操作就变成对于一个平面里的点 $(x, y)$ , 一次可以将它移动到 $(x \pm 1, y), (x, y \pm 1), (x + 1, y + 1), (x - 1, y - 1)$ 。
问题就转化为将所有点移动到同一个点，所用的最多步骤的最小值。
考虑二分一个步长 $mid$ , 那么在 $mid$ 步数内，一个点 $(x, y)$ 可以移动到的点构成一个凸多边形。
若所有多边形都有交集，则 $mid$ 是问题的一个解。

这个是凸的，所以可以线性规划理解，把周围的 $6$ 根线刻画出来。