张家港外贸网站建设,为什么上传网站模板网站上没有文字和图片,青岛做网站推广公司哪家好,wordpress个人博客多大空间登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;给出一个数n#xff0c;要求构造一个n的排列#xff0c;满足相邻两个数的差或和是一个奇质数
2n1e5
思路#xff1a;要满足相邻数的差或和是奇质数的话只有三种情况#xff0c;要么当前数a[i]a[i-1]pr…登录—专业IT笔试面试备考平台_牛客网
题目大意给出一个数n要求构造一个n的排列满足相邻两个数的差或和是一个奇质数
2n1e5
思路要满足相邻数的差或和是奇质数的话只有三种情况要么当前数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都能用此法构造出来只有如n12这种极少情况没有合法构造。
那么我们换一下a[1]令a[1]2发现n12时有了合法构造且发现无论是a[1]1还是a[1]2用到的最大的质数就是13那么我们猜想可以枚举极少的a[1]和质数就能得到合法答案所以我们从1~n枚举第一个数然后遍历后面的每一个位置从小到大遍历质数找到合法的数字就填进去最后检验一下所有数字收否都出现过如果不合法就换下一个a[1]。
赛后验证了a[1]要么等于1可以有合法构造1如果不行2就能有合法构造且用到的质数不超过5个也就是不大于13时间复杂度O(10n)
#includebits/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;cint;getprime();while (t--){solve();}return 0;
}
