BISHI29　小红的排列构造①¶

简单通过率 36.55%python3样例通过牛客 AC

牛客原题　源码

讲解章节：构造

一句话

构造排列 a，使所有 a_i + i 都不是质数。

解题思路¶

这题考什么¶

先想「最省事的排列」：恒等排列 a_i = i，此时 a_i + i = 2i。 2i 是偶数，只要 2i > 2 就一定不是质数；唯一的破绽是 i = 1 时 2i = 2，而 2 恰好是质数。所以只需要单独修掉下标 1。

修法：把位置 1 和位置 3 的值互换，得到 a = [3, 2, 1, 4, 5, ..., n]。

i=1: 3+1 = 4 = 2*2，合数；
i=2: 2+2 = 4，合数；
i=3: 1+3 = 4，合数；
i>=4: i+i = 2i >= 8，偶数且大于 2，合数。

全部满足，且这是一个合法排列。

n = 1：只有 [1]，1+1 = 2 是质数，无解； n = 2：[1,2] -> 2,4，2 是质数；[2,1] -> 3,3，3 是质数；也无解。所以 n <= 2 输出 -1，n >= 3 用上面的构造。

数据规模与复杂度¶

n <= 1e5，O(n) 生成 + 一次 " ".join 输出。完全不需要筛质数——构造保证了和恒为偶数（>=4），压根不用判素。

坑在哪¶

n = 2 同样无解。只特判 n = 1 会在 n = 2 时输出 [1,2] 或 [2,1]，两者分别产生和 2 与和 3，都是质数；
位置 1/3 的交换需要 n >= 3，n = 3 时刚好是 [3,2,1]；
输出是一行 n 个数，用 " ".join(map(str, ...)) 拼好后一次写出。逐个 print 既会把每个数打成单独一行（格式就错了），也会在 n = 1e5 时把 IO 变成整段程序里最慢的部分；
答案不唯一：满足「所有 a_i + i 都不是质数」的排列有很多个，题面样例给的 9 4 6 2 1 8 3 10 7 5 与本解法给的 3 2 1 4 5 ... 都算对。所以本地要用 special judge（特殊评测程序，按题目条件验证选手输出是否合法，而不是与标准答案逐字符比对）：本题配了 solutions/_spj/BISHI29.py，它先确认输出是 1..n 的排列，再筛出 [0, 2n] 内的质数逐位检查 a_i + i。

参考实现¶

solutions/BISHI29.py
import sys

n = int(sys.stdin.buffer.read().split()[0])
if n <= 2:
    print(-1)
else:
    a = list(range(1, n + 1))
    a[0], a[2] = a[2], a[0]           # 只需把下标 1 的 2 破掉
    sys.stdout.write(" ".join(map(str, a)) + "\n")

BISHI29 小红的排列构造①¶