题解：CF2171E Anisphia Wynn Palettia and Good Permutations

· · 题解

这题也不难啊，怎么是 *2000？

有一个很自然的思路是按照奇偶奇偶奇偶……这样填。但是对于奇偶奇这样不太行。那么我们考虑稍微浪费一点，这样填：奇偶偶奇偶偶奇偶偶……可以发现这样是可行的。

这样可以弄出长度为多少的数组？由于 1 \sim n 中有 \frac{n}{2} 个偶数，那么可以凑出 \frac{n}{4} 对“奇偶偶”，那么总共可以搞定 \frac{3n}{4} 个数。

还差一点。怎么弄呢？考虑延续这个思路，刚才把 2 的倍数都弄完了，考虑 3 的倍数，按照上面的方式填。这样，因为 1 \sim n 中是 3 的倍数但不是 2 的倍数的数有 \frac{n}{6} 个，可以凑出 \frac{n}{12} 组，那么就可以另外搞定 \frac{n}{4} 个数。显然这个不会正好是整的，会有一些边角余料，但是不难证明答案不会超过 6，于是就做完了。

实现时一个小细节：可以先放 2 的倍数，然后再放 6 的倍数，然后放 3 的倍数，这样衔接处不会产生额外的答案。

AC Record。