24.10.11

A

讨厌一个点的树这种没有边界感的东西。

猜结论：最少是菊花 \(2\) 个，最多是链 \(\left\lfloor \dfrac{n}{2} \right\rfloor + 1\)，从多到少就是把链上的点放到菊花上。

注意 \(1\) 个点时 \(1\) 是合法的。

B

翻转，KMP，从 \(r\) 往前跳 border 能跳就跳肯定不亏。

考场上使用分块维护每个点跳到上一个块最后哪个位置，喜提 \(O(n\sqrt n)\) 80pts。

找每个点的最短 border，倍增维护，复杂度 \(O(n \log n)\)。

C

/**
 * i < j
 * b[i]^b[j] < b[j]^b[i]
 * b[j] * lg(b[i]) < b[i] * lg(b[j])
 * lg(b[i]) / b[i] < lg(b[j]) / b[j]
 * lg(1) / 1 = 0
 * lg(2) / 2 = lg(4) / 4
 * lg(3) / 3 > lg(2) / 2 = lg(4) / 4
 * lg(i) / i > lg(i + 1) / (i + 1)  (i >= 4)
 * 
 * F(x):
 * 1 < (inf < inf - 1 < ... < 6 < 5) < 4 = 2 < 3
 * 
 * 不能出现相同数, 不能同时出现 2, 4
 * 枚举几种情况算一下顺序对逆序对...
 * 
 * - 一个数
 * - 1 < (k) < 2 / 3 / 4 : k 选两个 
 * - 1 < (k) < 2 < 3 : k 选两个
 * - 1 < (k) < 4 < 3 : k 选一个
 * - 1 < (k) : k 选三个
 */

选两个和选三个拿维护后缀的树状数组随便搞搞就有了。

D

Ag 佬都没改，弃之。