首页 > 代码库 > HDU 1016 Prime Ring Problem （素数筛+DFS）

HDU 1016 Prime Ring Problem （素数筛+DFS）

2024-07-14 22:23:44   216人阅读

题目链接

题意 ： 就是把n个数安排在环上，要求每两个相邻的数之和一定是素数，第一个数一定是1。输出所有可能的排列。

思路 : 先打个素数表。然后循环去搜。。。。。

 1 //1016 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5  6 using namespace std ; 7  8 bool vis[21]; 9 int prime[42] ,cs[21];10 int n ;11 12 void get_prime()13 {14     memset(prime,0,sizeof(prime));15     prime[1] = 1 ;16     for(int i = 2 ; i < 40 ; i ++)17     {18         if(prime[i] == 0)19         {20             for(int j = i*i ; j < 40 ; j += i)21                 prime[j] = 1 ;22         }23     }24 }25 26 void DFS(int s,int cnt)27 {28     if(cnt == n)29     {30         if(prime[cs[n]+1]) return ;31         for(int i = 1 ; i <= n - 1; i++)32             cout << cs[i] <<" " ;33         cout << cs[ n ]<<endl ;34         return ;35     }36     for(int i = 1 ; i <= n ; i++)37     {38         if(!vis[i] && !prime[s+i])39         {40             cs[++cnt] = i ;41             vis[i] = true ;42             DFS(i,cnt) ;43             cnt -- ;44             vis[i] = false ;45         }46     }47 }48 int main()49 {50     int casee = 1 ;51     get_prime() ;52     while(  cin >> n )53     {54         memset(vis,false,sizeof(vis)) ;55         cout << "Case "<<casee++ <<":" << endl ;56         vis[1] = true ;57         cs[1] = 1;58         DFS(1,1) ;59         cout << endl ;60     }61     return 0 ;62 }
View Code

 


联系
我们