HDU 1016 Prime Ring Problem(DFS回溯+素数判断)
http://acm.hdu.edu.cn/showproblem.php?pid=1016
题意:给你一个n,要求输出所有由1,2,3…n构成的素数环。所谓素数环就是该环中的任意相邻两个数的和是一个素数。且按字典序从小到大输出。
分析:本题在刘汝佳的入门经典里也有。
首先利用素数筛选法求出100以内的所有素数。
然后用dfs从小到大依次选取所有数字来构成环,注意当选完最后一个数的时候要用它和1(首位的数)判断是否他们的和是一个素数。
AC代码:
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100;
int n;
int prime[maxn];//prime[i]=0表i为素数,=1表i非素数
int ans[maxn],vis[maxn];
void get_prime()
{
memset(prime,0,sizeof(prime));
for(int i=2;i<maxn;i++)if(!prime[i])
{
for(int j=i*i;j<maxn;j+=i)
prime[j]=1;
}
}
void dfs(int pos)//当前正在构造ans素数环的第pos个位置
{
if(pos==n)
{
if(prime[ans[0]+ans[n-1]]==0)//头+尾=素数
{
printf("%d",ans[0]);
for(int i=1;i<n;i++) printf(" %d",ans[i]);
printf("\n");
}
}
else for(int i=1;i<=n;i++)if(!vis[i] && !prime[ans[pos-1]+i])
{
vis[i]=1;
ans[pos]=i;
dfs(pos+1);
vis[i]=0;//回溯
}
}
int main()
{
get_prime();
int kase=1;
while(scanf("%d",&n)==1)
{
printf("Case %d:\n",kase++);
memset(vis,0,sizeof(vis));
ans[0]=1;//素数环第一个位置固定为1
vis[1]=1;
dfs(1);
printf("\n");
}
return 0;
}
分享到:
相关推荐
HDU 1022 Train Problem I 附详细思路
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
Largest prime factor Everybody knows any number can be combined by the prime number. Now, your task is telling me what position of the largest prime factor. The position of prime 2 is 1, prime 3 is 2,...
ACM题库,一些题目和答案,以及解题报告,传上来共享
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
杭电OnlineJudge 200-2099的解题报告
搜索 dfs 解题代码 hdu1241
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门