ARC140

未补完

Link

A 让你最多改 \(k\) 个字符，最大化循环位移得到的本质不同的串。

枚举循环节，然后贪心判断即可。。复杂度 \(O(d(n)n)\)。

B 题意你有俩操作必须轮流做，\(\mathrm{ARC \to R},\mathrm{ARC\to AC}\)。

冷静思考一下发现最终有可能操作的一定是 \(R\) 旁边的数。

1操作相当于把 \(\mathrm{AAAAAAARCCCCCC}\) 这样极长长度-1。

2操作相当于把这个串删掉。

现在问题转化为你有 \(n\) 个数，交替让一个数-1,和删掉数。

注意 \(2\) 操作是让势能减少更多的，我们需要通过1让2操作减掉的势能尽可能少。

可以发现如果这个数是1，1，2操作等价。

所以现在 \(1\) 操作的任务就是在 \(2\) 删完 \(1\) 前尽可能多创造更多 \(1\)。（也就是首先减最小的，直到成为1）。

这样的正确性是得到保证的，考虑当 \(2\) 操作没有 \(1\) 的时候，我们无能为力只能先-1，然后删除。

---

C 题意让你构造出排列使得 \(A_i=|P_{i}-P_{i-1}|\) 的LIS尽可能长，特殊地，钦定了 \(P_1\) 的值。

不难想到构造 能使任何一种方案LIS至少为 \(N-2\) 。

如图

最大值 \(N-1\) 只能在 \(P_i=N/2\) 处取到，考虑这样的话 LIS就是 [1,2,3,...N-1] 那么从后面考虑这个是被确定的。

---

D 给你一个基环树森林有的点没有向外连边，你需要给他们指定出边，问所有情况的连通块个数。

我没有往基环树那面想。。。。。这个基环树的性质十分重要。

由于最终是基环树森林，所以连通块个数=环个数，环个数，，这样转化成了有标号计数，（就是我们按照标号的顺序连边）

变成了 \(\prod (1+w_x)\) 这种 egf 乘法，直接做 \(O(n^2\log n+n^2)\) 好像分治乘法能做到 \(O(n\log^2n)\) 但现在不是很清楚如何去掉 \(n^2\)。。。