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

即可。

【抽象】阴间题目记录

文章操作

CF612E Square Root of Permutation

CF1612E Messages

CF1659D Reverse Sort Sum

相关推荐

评论

【抽象】阴间题目记录