首页 > 试题广场 >

小红的排列构造

[编程题]小红的排列构造

热度指数：2214 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红希望你构造一个排列，满足对于排列中的每一项 $a_i$ 都满足： $a_i+i$ 均不是质数（下标 $i$ 从1开始）。你能帮帮她吗？

长度为 $n$ 的排列是指：一个长度为 $n$ 的数组，其中1到 $n$ 每个正整数恰好出现1次。例如[2,1,3]是排列，而[1,3,4,3]不是排列。

输入描述:

一个正整数，代表待构造的排列长度。

输出描述:

如果无法构造，则输出-1。
否则输出一个长度为的满足要求的排列。有多解时输出任意即可。

示例1

输入

输出

-1

说明

长度为1的排列只有[1]，由于1+1=2是质数，不合法。所以不存在可以构造的排列。

示例2

输入

输出

9 4 6 2 1 8 3 10 7 5

说明

，不是质数。
，不是质数。
，不是质数。
以此类推，每个元素加上均不是质数。符合要求。

算法知识视频讲解

kkkyd

发表于 2024-11-19 21:29:20

#include <iostream> using namespace std; //1和2是不可能的，3以上的数列前3位可以是3，2，1 //后面的4~n顺序排即可，后面的数与下标相等，ai+i=2*i，必然不是质数 int main() { int n; cin> 展开全文

Mag1c0nch

发表于 2024-11-20 21:33:23

简化题意：构造一个n的排列满足 i+a[i] 不是素数众所周知偶数都不是素数，可以考虑从这方面下手假设排列为正序排列，那么每一项都是 2*i ，都是偶数，显然只有 1 不合法因为 2*1 是素数，所以我们可以考虑对后续影响最小的改动方法考虑将 1 和 3 互换，发现合法，手玩一下可以发现 n 为 1 展开全文

Kato_Shoko

发表于 2024-11-19 20:31:02

特判1 2 3这些数据就行，因为后面的数据不需要改变，第i个就是i，i+i=2i，肯定不是质数。 #include <iostream> #include <queue> #include <map> #include <set> #include & 展开全文

宿伞之神

发表于 2024-11-20 00:10:28

发现n>=3一定有解，前三个构造 3 2 1 即可。 #include<bits/stdc++.h> #define int long long #define double long double #define x first #define y second using na 展开全文

是基德吖

发表于 2024-11-21 19:26:46

import java.io.*; import java.util.*; import java.math.BigInteger; public class Main { static void solve() { int n = in.nextInt(); 展开全文

mahongwei

发表于 2024-12-06 16:41:56

#include <iostream> #include <map> using namespace std; int main() { int n; while (cin >> n) { // 注意 while 处理多个 case 展开全文

yuyu1223

发表于 2024-12-01 16:03:42

import java.util.ArrayList; import java.util.List; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public sta 展开全文