2021.10.29模拟赛

Let out the cries imprisoned for so long

2021.10.29 模拟赛

A. 破门而入

就是问 $n$ 个不同元素划分成小于等于 $k$ 个环的数量

$O(n^2)$ 递推第一类斯特林数即可

B. 破门而入

发现字符串的重复仅出现在 $a\dots a$ 这样的情况下，这样包含 $a$ 和不含 $a$ 反转是一样的

所以最终答案是所有串减去每个字符出现个数两两匹配 即 $\binom{cnt}{2}$

C. 奶油蛋糕塔

把奶油当作点就是给边定向找最长路，发现大部分情况下直接找欧拉路选完就行，如果不存在欧拉路就删去最小的边

因为没欧拉路一定是四个奇点，删一个边会变成俩就有了，需要判一下能不能删，因为这个-30pts

D. 多重影分身之术

考过原题，然后没看T4，傻了

答案有单调性，直接二分贪心，每个点向左走，拿到左边没拿到的东西之后向右走