HDU - 1016  cxsys训练第一周&第二周

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. 

Note: the number of first circle should always be 1. 

 
Inputn (0 < n < 20). 
OutputThe output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order. 

You are to write a program that completes above process. 

Print a blank line after each case. 
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，但是最近想了一下可以用next_permutation做，结果TLE了，究其原因，就是深搜的时候剪枝做的比较好，所以运行的时间一对比（样例是n=18），会发现dfs的解法程序在不停的输出数据，但是STL的却仅仅是在闪光标。

    得结论：有的题剪枝的十分优雅（比如这题，如果1 2 判断不成立，那么第二个数放2这一大支直接剪掉了），便不能用next_permutation，有的题（比如李白打酒，一道蓝桥杯水题），便可以这样做（现在一想主要原因就是蓝桥杯这个只需要结果，而不限制时间），还有啊比如让你输出全排列，你用dfs会很慢，而next_per就相对来说快一点，各有优势吧，当不需要剪枝的时候，next_per感觉还是略占优势，毕竟内部是用swap实现的而不是深搜，但是对于有大剪枝的题，还是慎用吧！因为next_per是对每一个全排列在判断是否符合条件（即搜索树上已经到叶了，相当于完全暴力完全无剪枝）

下面上next_per的代码：（TLE）

#include<iostream> 
#include<algorithm>
#include<cstring>
using namespace std;
int a[35];
int cnt;
int su[70]; 
bool isPrime[55]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1};//写到37 
void init(int n) {
	for(int i = 1; i<=n; i++) {
		a[i]=i;
	}
}
bool ok(int n) {
	int i;
	for(i = 1; i<n; i++) {
		if(!isPrime[a[i]+a[i+1]]) return 0;
	}
	if(!isPrime[a[i]+a[1]]) return 0;
	return 1;
}
int main()
{
	int n;
	int iCase=0;
//	prime();
	while(~scanf("%d",&n)) {
		iCase++;
		printf("Case %d:\n",iCase);
		if(n==1) {
			printf("1\n");
		}
		memset(a,0,sizeof(a));
		init(n);
		do{
			if(ok(n)) {
				int i;
				for( i = 1; i<n; i++) {
					printf("%d ",a[i]);
				}
				printf("%d\n",a[i]);
			}
		}while(next_permutation(a+2,a+n+1));
		
		
		printf("\n");
	}
	return 0 ;
}


下面是dfs的代码：（用时608ms）

#include<iostream>
#include<cstring>
using namespace std;
void dfs(int step);
bool book[25];
int a[25];
int n;
bool isPrime[38] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1};  //0-37的打表 
int main()
{
	int cnt=1;
	while(scanf("%d",&n)!=EOF){
		memset(book,0,sizeof(book));
		memset(a,0,sizeof(a));
		a[1]=1;			//     别忘这个！！ 
		printf("Case %d:\n",cnt);
		cnt++; 
		dfs(2);
		printf("\n"); 
	}
	return 0 ;
}
void dfs(int step){
	if(step==n+1&&isPrime[a[step-1]+1]){
		for(int i=1;i<=n;i++){
			printf("%d",a[i]);
			if(i<n){
				printf(" ");	
			}
			else{
				printf("\n");
			}
			
		}
		return ;
	}
	for(int i=2;i<=n;i++){
		if(book[i]) continue;
		if(!isPrime[i+a[step-1]]) continue;
		book[i]=1;
		a[step]=i;
		dfs(step+1);
		book[i]=0;
	}
}