被迫营业.jpg

赛场上和 xgy 开黑成功过了 $6$ 题，上了大分十分开心。

D Coprime 2

考虑质因数分解，对每个数分解，对质数求并。

那么考虑每一个 $i$，同样质因数分解即可。

时间复杂度 $O(N\sqrt{N})$。

E Chain Contestant

设原先的字符串为 $t$。

设 $f_{i,S,j}$，表示前 $i$ 个里面某些比赛选了没选的状态为 $S$，最后一个选的比赛为 $j$。

分类讨论，如果 $t_i=j$ 并且 $S$ 里面包含 $t_i$，考虑钦定取 $t_i$，那么 $f_{i,S,t_i}=f_{i,S,t_i}+f_{i-1,S,t_i}$，同时对于一个不等于 $t_i$ 的且在 $S$ 中的 $l$，$f_{i,S,t_i}=f_{i,S,t_i}+f_{i-1,S-2^{t_i},l}$。

紧接着考虑钦定不选 $t_i$，也就是 $f_{i,S,j}=f_{i,S,j}+f_{i-1,S,j}$。

最后对所有的 $f_{n,S,j}$ 求和即可。

时间复杂度 $O(n2^{|\Sigma|}|\Sigma|)$。

F Dist Max 2

xgy KDT 草过去了并不讲 KDT 做法。

以下文字是 xgy 写的：

首先我们看看这个奇怪的距离：$\min (|x_i - x_j| , | y_i - y_j |)$。

假设这个距离 $\ge K$。

是不是意味着 $| x_i - x_j | \ge K$ 并且 $| y_i - y_j | \ge K$。

我们考虑二分这个 $K$，那么我们怎么判断这个 $K$ 是否满足条件呢？

如果一个 $K$ 能满足条件，我们一定能找到一个点 $(x_i,y_i)$ ，如果 $y$ 最小的那个点的 $x$ 坐标满足 $x_i-x \ge K$ ，即 $x_i - K \ge x$， 那么这个最小的 $y$ 一定满足 $y_i-y\ge K$，即 $y_i-K\ge y$，或这最大的 $y$ 坐标大于等于 $y_i+K$。

如果你按 $x$ 排序，这个判断过程可以做到 $O(n)$ 。