【题解】UVa 524 【Prime Ring Problem】

背景

这题当时学深度搜索的没有怎么认真搞,现在来搞,发现其实数据大的话,深搜也是超时的,和暴力差不多233。

分析

就是搜索当前每一位就好了

代码

#include<cstdio>
#include<algorithm>

namespace OI{
    using std::fill;
    using std::next_permutation;
}
using namespace OI;

int n;

const int MAXN = 666;
int primes[MAXN],mu[MAXN],phi[MAXN],num,A[MAXN];
bool isPrime[MAXN],hash[MAXN] = {false};

void sieve(){
    fill(isPrime,isPrime + MAXN,true);
    mu[1] = 1;phi[1] = 1;
    num = 0;
    for(int i = 2;i < MAXN;++i){
        if(isPrime[i]){
            primes[num++] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        static int d;
        for(int j = 0;j < num && (d = i * primes[j]) < MAXN;++j){
            isPrime[d] = false;
            if(i % primes[j] == 0){
                phi[d] = primes[j] * phi[i];
                mu[d] = 0;
                break;
            }else{
                phi[d] = (primes[j] - 1) * phi[i];
                mu[d] = -mu[i];
            }
        }
    }
    isPrime[0] = false;
    isPrime[1] = false;
}

void dfs(int cur){
    if(cur == n && isPrime[A[0] + A[n - 1]]){
        for(int i = 0;i < n;i++){
            if(i != 0){
                printf(" ");
            } 
            printf("%d",A[i]);
        }
        printf("\n");
    }else{
        for(int i = 2;i <= n;i++){
            if(!hash[i] && isPrime[i + A[cur - 1]]){
                A[cur] = i;
                hash[i] = true;
                dfs(cur + 1);
                hash[i] = false;
            }   
        }
    }
}


int main(){
    sieve();

    int id = 0;
    while(scanf("%d",&n) == 1 && n > 0){
        if(id > 0){
            printf("\n");
        }
        printf("Case %d:\n",++id);
        fill(hash,hash + n + n,false);
        A[0] = 1;
        dfs(1);
    }

    return 0;
} 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

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