题解：CF286A Lucky Permutation

AFO_Lzx · 2024-09-12 13:37:02 · 题解

题目传送门

\texttt{Description}

输入一个正整数 n ，输出一个长度为 n 的幸运数列，若没有输出 -1 。

\texttt{Solution}

这题一眼 DFS 全排列，不过 n \le 10^5 ，深搜时间复杂度肯定爆炸。

所以我们可以找规律。

如果 n=1，直接输出 1，因为当 n 为 1 时，唯一的幸运排列就是 1。

如果 n 是奇数，输出 -1 。因为在幸运排列的定义中，对于任何整数 i \ (1 \le i \le n) 都要满足特定条件，而当 n 为奇数时无法找到满足条件的排列。

如果 n 是偶数，进入循环生成幸运排列。循环从 1 开始，每次增加 2，遍历所有的奇数位置 i 。在每次循环中，先输出 i + 1 ，再输出 i ，这样就可以保证满足幸运排列的条件。

举个例子：

当 n = 4 时，先输出 2（即 i + 1 ，此时 i = 1），再输出 1（即 i），然后输出 4 和 3，形成 2 4 1 3 的排列，满足幸运排列的条件。

\texttt{Code}

代码很简单，就不贴了。