紫书搜索 例题7-4UVA - 524Prime Ring Problem

题目链接:

https://vjudge.net/problem/UVA-524

题意:

给一个n，要求生成1~n的排列，第一个数是1，相邻的两个数的和是素数，包括第一个和最后一个。

题解:

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 50+10; int n,isp[maxn],A[maxn],vis[maxn]; bool is_prime(int x){ int m = sqrt(x); for(int i=2; i<=m; i++) if(x%i==0) return false; return true; } void dfs(int cur){ if(cur == n+1 && isp[A[1]+A[n]]){ printf("%d",A[1]); for(int i=2; i<=n; i++) printf(" %d",A[i]); puts(""); return ; } for(int i=2; i<=n; i++){ if(!vis[i] && (isp[i+A[cur-1]])){ A[cur] = i; vis[i] = 1; dfs(cur+1); vis[i] = 0; } } } int main(){ int cas=1; while(scanf("%d",&n)!=EOF){ if(cas!=1) puts(""); MS(vis); MS(isp); for(int i=2; i<=n*2; i++) isp[i] = is_prime(i); printf("Case %d:\n",cas++); A[1] = 1; dfs(2); } return 0; }