J.Permutation and Primes

题目大意：

给定一个正整数 n ，构造一个 n 的排列，使得每对相邻元素的和或差的绝对值为一奇素数

提供一个思路：

可以将n分为三部分

1 4 7 10 13 16 19......

2 5 8 11 14 17 20......

3 6 9 12 15 18 21......

分为n%3！=1和n%3==1两种情况

n%3==1时 举个例子

1 4 7 10 13 16 19

2 5 8 11 14 17

3 6 9 12 15 18

此时可以构造出[1......19][12....3][2.....17] 但是此时还有两个数没有插入[15 18]

将[15 18]插入[8 11]之间即可(因为都相差7)

变成[1.....19][12....3][2...8 15 18 11 ...17]

n%3!=1时 举个例子

1 4 7 10 13 16 19

2 5 8 11 14 17 20

3 6 9 12 15 18 (21)........................有没有21都行

此时可以构造出[1....19][14........2][3............18] 但是此时还有两个数没插入[17 20]

将[17 20]插入[12 15]之间即可(因为都相差5)

变成[1....19][14......2][3...12 17 20 15....18]

当n比较小的时候打表

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
void solve();
vector<int>a1,a2,a3,ans;
int n,len1,len2,len3,now,len,id;
int main(){	
   int T;cin>>T;
   while(T--)solve();
    return 0;
}
void solve(){
   cin>>n;
   if(n==2){cout<<"1 2"<<endl;return;}
   if(n==3){cout<<"1 2 3"<<endl;return;}
   if(n==4){cout<<"4 1 2 3"<<endl;return;}
   if(n==5){cout<<"5 2 1 4 3"<<endl;return;}
   if(n==6){cout<<"5 2 1 4 3 6"<<endl;return;}
   if(n==7){cout<<"7 4 1 2 3 6 5"<<endl;return;}
   if(n==8){cout<<"7 4 1 2 3 6 5 8"<<endl;return;}
   if(n==9){cout<<"1 4 7 2 3 6 9 8 5"<<endl;return;}
   if(n==10){cout<<"1 4 7 10 5 2 3 6 9 8"<<endl;return;}
   len=len1=len2=len3=0;
   a1.clear(),a2.clear(),a3.clear(),ans.clear();
   for(int i=1;i<=n;i+=3)a1.push_back(i),len1++;
   for(int i=2;i<=n;i+=3)a2.push_back(i),len2++;
   for(int i=3;i<=n;i+=3)a3.push_back(i),len3++;

   if(n%3!=1){	
       for(int i=0;i<len1;i++)ans.push_back(a1[i]),len++;
       for(int i=len1-3;i>=0;i--)ans.push_back(a2[i]),len++;
       for(int i=0;i<len3;i++)ans.push_back(a3[i]),len++;
       now=a2[len2-2];
       for(int i=0;i<len;i++){
    cout<<ans[i]<<" ";
   	 if(now-ans[i]==5)
   	cout<<now<<" "<<now+3<<" ";
   	}
   }
   else {
       for(int i=0;i<len1;i++)ans.push_back(a1[i]),len++;
       for(int i=len3-3;i>=0;i--)ans.push_back(a3[i]),len++;
       for(int i=0;i<len2;i++)ans.push_back(a2[i]),len++;
       now=a3[len3-2];
   	for(int i=0;i<len;i++){
   		cout<<ans[i]<<" ";
   		if(now-ans[i]==7)
   		cout<<now<<" "<<now+3<<" ";
   	}
   }
   	cout<<endl;
   	return;
   }