Permutation and Primes 2023牛客暑期多校训练营8 J

登录—专业IT笔试面试备考平台_牛客网

题目大意：给出一个数n，要求构造一个n的排列，满足相邻两个数的差或和是一个奇质数

2<=n<=1e5

思路：要满足相邻数的差或和是奇质数的话只有三种情况，要么当前数a[i]=a[i-1]+prime[j]或a[i]=a[i-1]-prime[j]或a[i]=prime[j]-a[i-1]。

我们先随意设一个初值，不妨令a[1]=1，然后每一个位置都枚举质数也就是枚举j然后从上面三种情况里选一种，范围在1~n的且没有出现过的，构造一下发现大部分的n都能用此法构造出来，只有如n=12这种极少情况没有合法构造。

那么我们换一下a[1]，令a[1]=2，发现n=12时有了合法构造，且发现无论是a[1]=1还是a[1]=2，用到的最大的质数就是13，那么我们猜想可以枚举极少的a[1]和质数就能得到合法答案，所以我们从1~n枚举第一个数，然后遍历后面的每一个位置，从小到大遍历质数，找到合法的数字就填进去，最后检验一下所有数字收否都出现过，如果不合法就换下一个a[1]。

赛后验证了a[1]要么等于1可以有合法构造，1如果不行2就能有合法构造，且用到的质数不超过5个也就是不大于13，时间复杂度O(10n)

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const ll MOD = 998244353;
const int INF = 0x7fffffff;
ll n;
ll ans[N];
bool vis2[N];
int prime[2*N], tot = 0;
bool  vis[2*N];
void getprime()
{//欧拉线性筛for (int i = 2; i <= 2*N; i++){if (!vis[i]){prime[++tot] = i;}for (int j = 1; j <= tot; j++){if (i * prime[j] >= 2*N)break;vis[i * prime[j]] = 1;if (i % prime[j] == 0)break;}}
}
void init()
{for (int i = 1; i <= n; i++){vis2[i] = 0;}
}
void solve()
{cin >> n;init();for (int ii = 1; ii <= 2; ii++){ans[1] = ii;vis2[ii] = 1;int ma = 0;for (int i = 2; i <= n; i++){for (int j = 2; j <= 6; j++){ma = max(ma, prime[j]);int now1 = ans[i - 1] + prime[j];int now2 = ans[i - 1] - prime[j];int now3 = prime[j] - ans[i - 1];//每个数有三种选择if (now1 <= n && !vis2[now1]){//找一种合法的ans[i] = now1;vis2[ans[i]] = 1;break;}else if (now2 >= 1 && !vis2[now2]){ans[i] = now2;vis2[ans[i]] = 1;break;}else if (now3 <= n && now3 >= 1 && !vis2[now3]){ans[i] = now3;vis2[ans[i]] = 1;break;}}}//cout << ma << endl;//for (int i = 1; i <= n; i++)//{////	if (!vis2[i])//	{//		cout << i << endl;//	}//}bool flag = 1;for (int i = 1; i <= n; i++){//检验有没有没构造出来的数if (!vis2[i]){flag = 0;}vis2[i] = 0;}if (flag)break; 		}for (int i = 1; i <= n; i++){cout << ans[i] << " ";}cout << endl;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int t;cin>>t;getprime();while (t--){solve();}return 0;
}