AOJ 781.素数环|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% raw %}

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

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

1
5
0

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

题解

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

然后 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 < num_prime&&iprime[j] < maxn;j++) {
isNotPrime[iprime[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;
}

</div>

推荐订阅源

OhYee 博客

题目

题解

代码