2023-07-11

UOJ Round #21

A. 士兵调度

$limitn = 10^3$
$limitm = 10^3$
$minS = 10^3$

将第 $i$ 个士兵的坐标设为 $(i, i)$，对于 $m = n - 1$ 次移动，第 $i$ 次移动将第 $i + 1$ 个士兵挪到第 $1$ 行，这样总变化次数恰好为 $n$。

$limitn = 10^5$
$limitm = 300$
$minS = 94500$

将一个 $400 \times 500$ 的棋盘黑白染色，在所有黑格上放上士兵，每次操作将相邻列士兵合并，$n$ 个士兵所属的分组恰好变化一次，操作步数只需 $250$。

$limitn = 10^5$
$limitm = 10^5$
$minS = 21100000$

对于一组 $y$ 坐标相同的士兵，设其中有 $a$ 人分组为第二组。

按照分组规则，这些士兵所属的 $x$ 坐标上一定分别有不少于 $a$ 名士兵，故而 $a$ 一定不超过 $\sqrt{n}$。

对于 $x$ 坐标进行同样分析，就知道了每次操作后分组变化次数一定不超过 $2 \sqrt{n}$。

注意到每次操作时合并的两行中，较小的那一行贡献的变化次数可以用启发式合并的来分析，这一部分的步数总和是 $n\log n$，所以总的变化次数的界为 $m \sqrt{n} + n \log{n} + \mathcal O(n + m)$。

将操作分为若干轮执行。

对于第 $T$ 轮，我们需要将点集由 $(T - 1) \times (T - 1)$ 的正方形增加一行一列变为 $T \times T$ 的正方形，这样在该轮中所有 $(T - 1) \times (T - 1)$ 个原正方形中的点的分组都会变化一次。

先在平面远处预先放好点，用到时再移过来。

注意由于两维坐标的不对称性，实现时需要注意增加行和增加列的先后顺序。

这样的操作不一定能恰好契合 $n, m$ 的大小，截取按照这种构造方法生成的前 $n$ 个点，再将前 $n - m$ 个点在所有操作开始前就摆在它最后应在的位置上。

总操作步数大约为 $\sum_{i = n - m + 1}^{n} \sqrt{i}$。

$n \le 20$

暴力。

$n \le 100$

自底向上进行 DP，记 $f_{k, n}$ 表示 $k$ 层 $n$ 个点的答案，特别地 $f_{0, n} = [n = 1]$。

\[f_{k, n} = \sum_{m = 0}^{n - 1} \binom{n - 1}{m} f_{k - 1}{m} [n - 1 - m \equiv 0 \pmod 2]\]

时间复杂度 $\mathcal O(k n^2)$。

$n \le 3 \times 10^3$

使用 FFT 优化。

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