NC247980. 排列
描述
输入描述
一行一个正整数 。
数据保证 。
输出描述
如果无解,输出一行 "NO"。否则输出两行,第一行一个字符串 "YES"(均不含引号),接下来一行 个正整数 ,描述这个排列。如果有多组解,输出任意一组即可。
示例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; }