HDU 1016 Prime Ring Problem

分手后的思念是犯贱 2022-04-16 05:54 202阅读 0赞

## 原题目链接[HDU1016][] ##

--------------------

## 分类 ##

HDU 素数 DFS

--------------------

## 题意 ##

输入一个数n,把1到n的自然数放到一个环里，保证相邻的两个数的和是素数。  
![1016-1.gif][]

--------------------

## 样例输入输出 ##

Sample Input

6
    8

Sample Output

Case 1:
    1 4 3 2 5 6
    1 6 5 2 3 4
    
    Case 2:
    1 2 3 8 5 6 7 4
    1 2 5 8 3 4 7 6
    1 4 7 6 5 8 3 2
    1 6 7 4 3 8 5 2

--------------------

## 想法 ##

DFS基础题，注意深搜结束条件

--------------------

## 代码 ##

249ms

#include<bits/stdc++.h>
    using namespace std;
    const int maxn =  1111;
    int get_prim[maxn]={ 0};
    int circle[maxn],vis[maxn],n;
    void Get_prim(){ //素数打表 1表示不是素数 
        get_prim[1] = 1; 
    	for(int i=2;i<=maxn;i++){ 
    		if(!get_prim[i]){ 
    			for(int j=i*i;j<=maxn;j+=i){ 
    				get_prim[j] = 1;
    			}
    		}
    	}
    }
    
    void dfs(int step){ 
    	if(step==n+1&&!get_prim[circle[1]+circle[n]]){ //深搜结束条件 
    		for(int i=1;i<n;i++)
    			printf("%d ",circle[i]);
    		printf("%d\n",circle[n]);
    	}else{ 
    		for(int i=2;i<=n;i++){ 
    			if(!vis[i]&&!get_prim[circle[step-1]+i]){ 
    				circle[step] = i;//把符合要求的数存入数组 
    				vis[i] = 1;//标记 
    				dfs(step+1);
    				vis[i] = 0;//回溯 
    			}
    		}
    		
    	}
    }
    int main() { 
    	//freopen("in.txt","r",stdin);
    	Get_prim();
    	int kase=0;
    	while(cin >> n&&n){ 
    		memset(vis,0,sizeof(vis));
    		circle[1] = 1;
    		printf("Case %d:\n",++kase);
    		dfs(2);
    		printf("\n");
    	}
    	return 0;
    }

[HDU1016]: http://acm.hdu.edu.cn/showproblem.php?pid=1016
[1016-1.gif]: /images/20220416/cacf4b05766941aa98d444b125feb98f.png