henrytb 的博客

henrytb 的博客

题解 UVA524 【素数环 Prime Ring Problem】

posted on 2019-02-11 19:34:50 | under 题解 |

刘汝佳大法好!

我又来介绍刘汝佳大法了QAQ(见紫书)

对于这道题呢,我们可以使用两种方法:

  1. 生成-测试法(next_permutation)

  2. 搜索:回溯法

我们发现:生成-测试法的时间复杂度是 $O(n!)$ (因为 $1\sim n$ 的排列共有 $n!$ 个),在 $n$ 比较大是已经超时。

所以我们使用回溯法。

PS:此题的输出很毒瘤,行末不能有空格&&最后没有多余回车

我就被坑了QAQ

代码如下:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
bool prime[100],used[100];
int n,a[100],now;
void dfs(int deep){
    if(deep==n+1&&prime[a[1]+a[n]]){
        rep(i,1,n){
            printf("%d",a[i]);
            if(i!=n)printf(" ");
        }
        puts("");
        return;
    }
    rep(i,2,n){
        if(prime[i+a[deep-1]]&&!used[i]){
            used[i]=true;
            a[deep]=i;
            dfs(deep+1);
            used[i]=false;
        }
    }
}
int main(){
    prime[2]=prime[3]=prime[5]=prime[7]=prime[11]=prime[13]=prime[17]=prime[19]=prime[23]=prime[29]=prime[31]=true;  //每日打表心情好
    bool isf=false;
    while(~scanf("%d",&n)){
        a[1]=1;
        if(isf)puts("");
        isf=true;
        printf("Case %d:\n",++now);
        memset(used,false,sizeof(used));
        dfs(2);
    }
    return 0;
}