是时候总结一些 konata 给的 trick 了。

根 号 分 治

[A]

自然数分拆是可以写成两种形式的。

如果从背包的角度考虑，我们有方程 $f{i,j}=f{i-1,j}+f_{i,j-i}$ 。

但是如果从第二类stirling数的方面去考虑，我们有方程 $f{i,j}=f{i-1,j-1}+f_{i-j,j}$

(konata吟唱完毕)

回到这一题，我们发现，如果我们只是任意选择一种方法去DP，时间复杂度是 O(n^2) 的，除非数据造水了，否则是无法通过此题的。

但是如果我们把两个结合一下呢？

我们使用第一个方程式处理 i \leq \sqrt n 的情况，使用第二个方程式处理 i>\sqrt n 的情况。注意第二方程式要稍稍改一下变成 $f{i,j}=f{i-m,j-1}+f_{i-1,j}$

然后照着做一遍就可以了，时间复杂度 O(n \sqrt n)

[B]

我们首先发现，答案具有单调性，然后直接二分

还是先想想单次做法是什么吧。

首先肯定我们可以 O(n) 树形DP求取第一次的答案。

同时我们发现，答案是类似整除分块一样的下降（也就是前面下降的多，后面下降的少）。

于是我们对于前 \sqrt n ，直接暴力求答案，对于后半部分，由于答案有单调性，因此二分找到当前段答案都一样的位置，将这一段都赋值为这个答案。

注意 i=1 的答案为 n。

人 类 智 慧

[D]

首先我们可以了解一些刚性碰撞的trick。

1)掉头->穿过

2)相对顺序不变

有了这两条性质，我们就可以将原序列按坐标排序，二分出时间。

对于这个时间求取答案，可以再次二分，但我们注意到由于你已经提前排好序了，时间也是固定的，因此完全可以双指针(two-point) 解决。

[E]

什么移球游戏，明明是构造。

随 机 算 法

[F]

非常推荐大家看一下原题的图，会有发现
首先枚举并求带答案这个是可以暴力DFS的。
但是改进呢？
我们不妨设答案就是第 i 个人的子集，在这个限制条件下再去做。
然后这个东西可以通过高位前缀和解决，时间复杂度 O(n\cdot 2^n)
但是我们怎么制定第 i 个人呢？
随机！！！
随机50次就可以了。

[H]

在前一题的基础上，我们再次考虑随机算法。
首先答案一定不超过 n，因为可以将所有奇数+1从而使数列的gcd变为2.
因此必有一半及以上的元素不变、加1 或减 1。
我们每次随机出 a_k ，然后将 a_k+1 a_k a_k-1 都分解质因数后加入SET。
最后从遍历 SET 判断每个数要是这个数的倍数至少付出的代价。

[I]

反而应该是随机化里面最简单的一题。
直接给每个点随机黑白染色，每次规定只能黑点往白点走/白点往黑点走，这样从 1 走 k 步回到 1 付出的最小代价。
然后取最小值就可以了。