CF2118B Make It Permutation 题解
Mier_Samuelle
·
·
题解
以 n=5 为例，我们尝试构造下面的「循环」矩阵：
\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 2 & 3 & 4 \\ 4 & 5 & 1 & 2 & 3 \\ 3 & 4 & 5 & 1 & 2 \\ 2 & 3 & 4 & 5 & 1 \end{bmatrix}
不难发现，对于任意 1 \le i \le n，依次反转 [1,n],[1,i-1],[i,n] 三个区间即可做到。
然后手玩几组数据，我们发现反转 [1,n] 其实是没有用的，故我们可以在 2n 次操作内完成目标。
CF 提交记录