紫书搜索例题7-4 UVA

题目链接:

题意:

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

题解:

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 50+10;
17 int n,isp[maxn],A[maxn],vis[maxn];
18 
19 bool is_prime(int x){
20     int m = sqrt(x);
21     for(int i=2; i<=m; i++)
22         if(x%i==0) return false;
23     return true;
24 }
25 
26 void dfs(int cur){
27     if(cur == n+1 && isp[A[1]+A[n]]){
28         printf("%d",A[1]);
29         for(int i=2; i<=n; i++)
30             printf(" %d",A[i]);
31         puts("");
32         return ;
33     }
34 
35     for(int i=2; i<=n; i++){
36         if(!vis[i] && (isp[i+A[cur-1]])){
37             A[cur] = i;
38             vis[i] = 1;
39             dfs(cur+1);
40             vis[i] = 0;
41         }
42     }
43 }
44 
45 int main(){
46     int cas=1;
47     while(scanf("%d",&n)!=EOF){
48         if(cas!=1) puts("");
49         MS(vis); MS(isp);
50         for(int i=2; i<=n*2; i++) isp[i] = is_prime(i);
51         printf("Case %d:
",cas++);
52         A[1] = 1;
53         dfs(2);
54 
55     }
56 
57     return 0;
58 }

紫书搜索 例题7-4 UVA

题目链接:

题意:

题解:

代码:

紫书搜索例题7-4 UVA