【抽象】阴间题目记录

· · 题解

CF612E Square Root of Permutation

考虑 i\to p_i 连边，发现会形成若干个偶环和奇环，再考虑平方后环的变化，发现奇环依旧是奇环，但是会变成先原环上奇数点后偶数点，偶环则是会分裂为两个点数相等的偶环，两两匹配即可。

CF1612E Messages

发现 k 范围非常小，猜想一个结论：最多选取不超过 \max{k_i} 个。

证明：考虑归纳法。记 s=\max\{k_i\}。当 t\gt s 时，原先选的数贡献不变，因此选择 s 个的方案选的数会保留。

记 f_i 表示第 i 大的贡献，ans_i 表示选择 i 个时的答案，那么 ans_{s+1}=ans_s\times\frac{s}{s+1}+\frac{f_{s+1}}{s+1}。ans_s 与 ans_{s+1} 作差后得 \frac{ans_s}{s+1}-\frac{f_{s+1}}{s+1}，由于 f 单调不增，所以 ans_s\ge ans_{s+1}。其它归纳可证。

然后暴力做就行了。

CF1659D Reverse Sort Sum

注意到对于一个位置 i，对于能够包含它的 f(j,A)（即 j\ge i），这个位置一定是先有一段 1 然后剩下的全为 0。于是我们考虑用前面的位置来确定后面的位置，然后填 0。

然后我们有 c_i=0 的位置 a_i 一定是 0，第一个不为 0 的位置一定是 1。

剩下的分讨 a_i 为 0 和 1 即可。