题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1016
题目大意:有n个数字,编号分别为1-n.要组成一个素数环.素数环就是相邻两个值加起来是个素数.第一个位置默认是1.由于n<20.所以和最大是19+18=37.所以可以先把38以前的素数和非素数用0和1区别开.
ACM的输入输出建议全部使用C风格的.因为C++的相比较慢,即使写了ios::sync_with_stdio(false)和cin.tie(0).就这题而言.C语言的只用了400ms.而C++的用了1300ms.原因是C++多了个输入输出的缓冲区.多了一部分的拷贝时间…所以这就是很多题目.明明和AC代码一样.但就是超时的原因.
AC代码:
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define Size 21
/*//打数素数环.可以先打好素数表.然后去查表...//题目要求打印所有的情况.则只能用dfs去全部遍历. */
int n;
int visit[Size];
int world[Size];
//素数表.从0开始.1代表素数.0代表非素数.
int list[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 };//pos代表已经确定好的数字的个数.
void dfs(int pos)
{//当下标到了最后一个时.if (pos == n){//如果成立则打印.注意最后没有空格.if (primelist[world[pos - 1] + world[0]] == 1){printf("%d", world[0]);for (int i = 1; i < n; ++i){printf(" %d", world[i]);}printf("\n");}}else{//这里i表示将要放的数字.for (int i = 2; i <= n; ++i){//进行条件筛选.if (visit[i] == 0 && list[i + world[pos - 1]] == 1){visit[i] = 1;world[pos] = i;dfs(pos + 1);//回溯.visit[i] = 0;}}}
}int main()
{int count = 1;while (scanf("%d", &n) != EOF){memset(visit, 0, sizeof(visit));printf("Case %d:\n", count++);//从下标为1开始.因为第一个数默认是1.world[0] = 1;dfs(1);printf("\n");}return 0;
}