列表

详情


NC247980. 排列

描述

请注意本题不同寻常的时间限制。
给定一个正整数 n,试构造一个 的排列 p 满足如下条件:
-
-

其中 为质数集。

输入描述

一行一个正整数 n

数据保证

输出描述

如果无解,输出一行 "NO"。

否则输出两行,第一行一个字符串 "YES"(均不含引号),接下来一行 n 个正整数 p_i,描述这个排列。

如果有多组解,输出任意一组即可。

示例1

输入:

8

输出:

YES
6 5 8 7 2 1 4 3

示例2

输入:

2

输出:

NO

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 1127ms, 内存消耗: 118344K, 提交时间: 2023-02-03 22:53:34

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 50000

int i,j,k,n,m,t,p[N+50],vis[N+50],x,y,res;

struct SB{
	int pl[N+50],pr[N+50],visl[N+50],visr[N+50],n,m,i,j,k,it;
	vector<int> vl[N+50],vr[N+50];
	void init(int n0,int m0){
		n=n0;m=m0;it=0;
		for(i=1;i<=n;i++){
			visl[i]=0;pl[i]=-1;vl[i].clear();
		}
		for(i=1;i<=m;i++){
			visr[i]=0;pr[i]=-1;vr[i].clear();
		}
	}
	void add(int x,int y){
		vl[x].push_back(y);
		vr[y].push_back(x);
	}
	bool dfsl(int x){
		if(visl[x]==it)return 0;
		visl[x]=it;
		for(auto i:vl[x]){
			if(pr[i]==-1){
				pl[x]=i;pr[i]=x;return 1;
			}
		}
		for(auto i:vl[x]){
			if(visl[pr[i]]!=it&&dfsl(pr[i])){
				pl[x]=i;pr[i]=x;return 1;
			}
		}
		return 0;
	}
	bool dfsr(int x){
		if(visr[x]==it)return 0;
		visr[x]=it;
		for(auto i:vr[x]){
			if(pl[i]==-1){
				pr[x]=i;pl[i]=x;return 1;
			}
		}
		for(auto i:vr[x]){
			if(visr[pl[i]]!=it&&dfsr(pl[i])){
				pr[x]=i;pl[i]=x;return 1;
			}
		}
		return 0;
	}
	bool getl(int x){
		it++;return dfsl(x);
	}
	bool getr(int x){
		it++;return dfsr(x);
	}
}sb;

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	
	for(i=2;i<=N;i++){
		if(!vis[i]){
			p[++m]=i;
			for(j=i;j<=N;j+=i){
				vis[j]=1;
			}
		}
	}
	
	cin>>n;
	if(n<8||n&1||n>=20000){
		cout<<"NO";return 0;
	}
	sb.init(n,n);
	
	for(i=1;i<=m;i++){
		for(j=i+1;j<=m;j++){
			x=(p[j]-p[i]);
			y=(p[j]+p[i]);
			if(x&1)continue;
			x/=2;y/=2;
			if(1<=x&&x<=n&&1<=y&&y<=n){
				sb.add(x,y);
				sb.add(y,x);
			}
		}
	}
	
	for(i=1;i<=n;i++){
		if(!sb.getl(i)){
			cout<<"NO";return 0;
		}
	}
    
    cout<<"YES\n";
	for(i=1;i<=n;i++){
		cout<<sb.pl[i]<<' ';
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 5297ms, 内存消耗: 513252K, 提交时间: 2023-02-03 21:26:45

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
const int N = 200010;
const int MN = 200000;
int n,m,x,tt,bj[N],ans[N],id[N];
bool gg[N],use[N],ok[N];
vector<int>zs,to[N];
inline void get(){
	int cnt=0;
	for(int i=2;i<=MN;i++){
		if(gg[i]) continue;
		if(i!=2) zs.push_back(i);
		for(int j=i+i;j<=MN;j+=i){
			gg[j]=1;
		}
	}
}
inline bool judge(int x,int y){
	if(gg[x+y] || gg[abs(x-y)]) return 0;
	return 1;
}
bool find(int u){
	for(auto t:to[u]){
		if(bj[t]==tt) continue;
		bj[t]=tt;
		if(!ans[t] || find(ans[t])){
			ans[u]=t;
			ans[t]=u;
			return 1;
		}
	}
	return 0;
}
inline bool cmp(int u,int v){return to[u].size()<to[v].size();}
inline void work() {
	get();
	cin>>n;
	if(n&1){
		puts("NO");
		return;
	}
	int cnt=0;
	for(int i=1;i<=n;i+=2){
		for(auto t:zs){
			if(t<i){
				if(!gg[2*i-t]){
					to[i].push_back(i-t);
				}
			}
			if(t>i && t+i>n) break;
			if(i+t<=n && !gg[2*i+t]){
				to[i].push_back(i+t);
			}
		}
	}
	
	for(int i=1;i<=n;i+=2) id[(i+1)/2]=i;
	sort(id+1,id+n/2+1,cmp);
	
	for(int i=1;i<=n/2;i++){
		tt++;
		if(!find(id[i])){
			puts("NO");
			return;
		}
	}
	puts("YES");
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}

int main () {
	int t;
	t=1;
	while (t --) work();
	return 0;
}

上一题