ARC140

未补完

Link

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

枚举循环节，然后贪心判断即可。。复杂度 $$。

B 题意你有俩操作必须轮流做，$$。

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

1操作相当于把 $$ 这样极长长度-1。

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

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

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

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

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

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

---

C 题意让你构造出排列使得 $$ 的LIS尽可能长，特殊地，钦定了 $$ 的值。

不难想到构造 能使任何一种方案LIS至少为 $$ 。

如图

img1

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

---

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

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

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

变成了 $$ 这种 egf 乘法，直接做 $$ 好像分治乘法能做到 $$ 但现在不是很清楚如何去掉 $$。。。