AOJ 781.素数环

235


题目


点击显/隐题目

把1-20这20个数摆成一个环,要求相邻的两个数的和是一个素数。编写程序,对给定的第一个数m,打印出满足条件的一种排列顺序。如果有多组解,输出字典序最小的一组。





包括多组测试数据,每组测试数据占一行,并且只有一个整数m,(0<=m<=20),当m=0时,表示输入结束。





对每组测试数据输出一行结果,结果为第一个整数为m的一种排列序列,序列中共有20个整数,各数之间用空格分隔。如果有多组解,输出字典序最小的一组。





1
5
0





1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
5 2 1 4 3 8 9 10 7 6 11 20 17 12 19 18 13 16 15 14





题解



相邻两个数(包括第一个数和最后一个数)的和为素数
因此先筛法求素数打个素数表方便后面查询

然后 DFS 暴力搜索所有情况(按照字典序顺序)
找到所有都满足的就输出出来即可

每一行最后一个数后面没有空格需要注意下

只有 20 组输入,可以打表

~~这道题最早数据没有考虑到首位两个数,所以没人 AC 中午找老师改了下数据~~


代码


点击显/隐代码
`cpp 素数环 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 45;

int prime[maxn] = {0},num_prime = 0;
bool isNotPrime[maxn] = {1,1};

void Prime() {
for(long i = 2;i < maxn;i++) {
if(!isNotPrime[i])prime[num_prime++] = i;
for(int j = 0;j < numprime&&iprime[j] < maxn;j++) {
isNotPrime[i*prime[j]] = true;
if(!(i%prime[j]))break;
}
}
}

bool vis[maxn / 2];
int List[maxn / 2];
int pos;
bool dfs(){
if(pos == 20) {
if(isNotPrime[List[19] + List[0]])
return false;

bool first = true;
for(int i = 0;i < 20;i++) {
if(!first)
printf(" ");
first = false;
printf("%d",List[i]);
}
return true;
}
for(int i = 1;i <= 20;i++) {
if(vis[i])
continue;
if(isNotPrime[List[pos - 1] + i])
continue;
List[pos++] = i;
vis[i] = true;
if(dfs())
return true;
vis[i] = false;
pos--;
}
return false;
}

bool Do() {
int n;
scanf("%d",&n);
if(n == 0)
return false;
memset(vis,false,sizeof(vis));
pos = 0;

List[pos++] = n;
vis[n] = true;
dfs();
printf("n");

return true;
}

int main() {
Prime();
while(Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论