HDU1016

题目链接

传送门

题目大意

题目大意是说要求输出所有素数环,保证任意相邻两个数相加是素数,这里特别注意判断下第一个数和最后一个数相加是否是素数。

解题思路

数据不是太大,所以先把素数表写出来,开个vis数组来表示数字是否被标记过,v数组来存储最后的输出结果,
v[1]=1。从2开始DFS搜索,如果s等于n + 1,说明已经搜索完毕,此时首尾作特殊判断。否则的话从2到n开始遍历,如果vis[i]没有被标记,并且 i 和上一个保存的数字num[s-1]加起来也是个素数的话,把 i 入num数组,vis[i]标记为1,接下来搜索dfs( s + 1 ),最后记得回溯,把vis[i]置回0。

参考代码

#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <string>  
#include <vector>  
#include <list>  
#include <map>  
#include <queue>  
#include <stack>  
#include <bitset>  
#include <algorithm>  
#include <numeric>  
#include <functional>  
using namespace std;  
#define REP(i, n) for (int i=0;i<int(n);++i)  
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)  
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)  
#define REP_1(i, n) for (int i=1;i<=int(n);++i)  
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)  
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)  
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)  
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)  
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)  
#define REP_N(i, n) for (i=0;i<int(n);++i)  
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)  
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)  
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)  
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)  
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)  
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)  
#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)  
#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)  
#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)  
#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)  
#define Display(A, n, m) {                      \  
    REP(i, n){                                  \  
        REP(j, m) cout << A[i][j] << " ";       \  
        cout << endl;                         \  
    }                                           \  
}  

#define Display_1(A, n, m) {                    \  
    REP_1(i, n){                                \  
        REP_1(j, m) cout << A[i][j] << " ";     \  
        cout << endl;                         \  
    }                                           \  
}  
typedef long long LL;  
typedef double DB;  
typedef unsigned UINT;  
typedef unsigned long long ULL;  

typedef vector<int> VI;  
typedef vector<char> VC;  
typedef vector<string> VS;  
typedef vector<LL> VL;  
typedef vector<DB> VD;  
typedef map<int, int> MII;  
typedef map<string, int> MSI;  
typedef map<LL, int> MLI;  
typedef map<DB, int> MDI;  
typedef pair<int, int> PII;  
typedef pair<int, bool> PIB;  
typedef pair<LL, LL> PLL;  
typedef vector<PII> VII;  
typedef vector<VI> VVI;  
typedef vector<VII> VVII;  
const int dx[] = {-1, 0, 1, 0};  
const int dy[] = {0, 1, 0, -1};  

const int MOD = 1000000007;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 1LL << 60;  
const DB EPS = 1e-9;  
const DB OO = 1e15;  
const DB PI = acos(-1.0);  
#define N 51  
int n , i , j ,k;  
int num[N] , vis[N] , v[N];  
int ispri[] = {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,0,0,0};  

void dfs(int s)  
{  
    if(s == n + 1)  
    {  
        if(ispri[v[s - 1] + 1])  
        {  
            FOR_1(i , 1 , n)  
                printf("%d%c",v[i],i == n ? '\n' : ' ');  
        }  
    }  
    else  
    {  
        FOR_1(i , 2 , n)  
        {  
            if(!vis[i] && ispri[i + v[s - 1]])  
            {  
                vis[i] = 1;  
                v[s] = i;  
                dfs(s + 1);  
                vis[i] = 0;  
            }  
        }  
    }  
}  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int cas = 1;  
    while(~scanf("%d",&n))  
    {  
        memset(vis , 0 , sizeof(vis));  
        v[1] = 1;  
        printf("Case %d:\n",cas);  
        dfs(2);  
        cas++;  
        printf("\n");  
    }  
}  

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图