hduoj 1016 素数环 DFS +筛选法求素数

素颜马尾好姑娘i 2024-02-18 23:08 47阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> <h2>Prime Ring Problem</h2> Time Limit: 4000/2000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 66383&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 28451 &nbsp; Problem Description 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. <img alt="" src="http://acm.hdu.edu.cn/data/images/1016-1.gif"> &nbsp; &nbsp; Input n (0 &lt; n &lt; 20). &nbsp; &nbsp; Output The 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. &nbsp; &nbsp; Sample Input <pre><code>&nbsp;</code></pre> 6 8 &nbsp; &nbsp; Sample Output <pre><code>&nbsp;</code></pre> 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 &nbsp; &nbsp; Source <a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=Asia+1996%2C+Shanghai+%28Mainland+China%29&amp;source=1&amp;searchmode=source" rel="nofollow">Asia 1996, Shanghai (Mainland China) </a> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

刚开始用全拍列，超时了，然后自己想了想，DFS应该可以，我心里正想着DFS也应该超时，没想到a了，^\_^

312ms，这是我做出来的第一道搜索题。加油，蓝孩！Jeep，加油！加油，为了父母。

再做一遍，居然没做出来，输入如果奇数，则输出No Answer，这点可以加速。

#include<iostream>
 using namespace std;
 int prim[50]={0};
 int n,k=1;
 bool c[30];
 int b[30];
 int df=0;
 void dfs(int d,int f)
 {
 	int i,j;
 	if(f-1==n&&!prim[d+b[1]])
 	{
 		df=1;
 		b[f]=d;
 		for(i=1;i<=n;i++)
 		if(i==1)
 		printf("%d",b[i]);
 		else
 		printf(" %d",b[i]);
 		printf("\n");
 		return ;
 	}
 	else
 	for(i=1;i<=n;i++)
 	{
 		if(!c[i]&&!prim[i+b[f-1]])
 		{
 			c[i]=true;
 			b[f]=i;
 			dfs(i,f+1);
 			c[i]=false;
 		}
 	}
 }
 int main()
 {
 	prim[0]=1;
 	prim[1]=1;
 	for(int i=2;i<50;i++)
 	{
 		for(int j=2;j*i<50;j++)
 		{
 			prim[i*j]=1;
 		}
 	}
 	
 	int m;
 	while(~scanf("%d",&n),n)
 	{
 	 printf("Case %d:\n",k++);
 		if(n&1&&n!=1)
 		{
 			printf("No Answer\n");
 			continue;
 		}
 		c[1]=true;
 		b[1]=1;
 		
 		dfs(1,2);
 		
 		if(!df)
 		{
 			printf("No Answer\n");
 		}
 		df=0;
 	}
 	return 0;
 }