题解 UVA524 素数环 Prime Ring Problem

· · 题解

这道题的思路和P1706 全排列问题相似

从第一层开始搜索直到越界，当越界的时候来输出。

但是这题的输出问题一定要注意,从第二组开始就有换行,同时每组数据的最后没有空格

请勿抄袭

代码如下：


#include<bits/stdc++.h>//万能头真好用
using namespace std ;

int t ;
int ans[20] ;//存答案
bool vis[20] ;//判断这个数有没有取过

bool prime( int x )//判断素数,会更高端写法的可跳过QAQ
{
    if ( x == 0 || x == 1 ) return 0 ; 
    for ( int i = 2 ; i <= sqrt(x) ; i++ )//一个小优化,只需要枚举到√n
    {
        if ( x % i == 0 ) return 0 ;
    }
    return 1 ;
}

void dfs( int x ) 
{
    if ( x == t + 1 && prime ( ans[t] + ans[1] ) )/*当满足条件以及开头和末尾和是素数,这里补足没有判断首尾的情况*/
    {
        for ( int i = 1 ; i <= t - 1 ; i++ )
        {
            cout << ans[i] << " " ; 
        }
        cout << ans[t] << endl ;
    }
    for ( int i = 2 ; i <= t ; i++ )//从第二层开始因为第一层是1  
    {
        if ( prime ( i + ans[x - 1] ) && vis[i] == 0 )//如果这个数加上前一层的数的和是质数,并且这个数还没有被用过 
        {
            ans[x] = i ;//把这个数放进这一层 
            vis[i] = 1 ;//把这个数标记为用过了
            dfs( x + 1 ) ;//搜索下一层 
            ans[x] = 0 ;//回溯 
            vis[i] = 0 ;
        }
    }
}
int main()
{
    //freopen("a.txt","w",stdout) ;
    /*这行代码主要是用来在存代码的那个文件夹里生成一个a文件,将代码的输出提取到这个文件里面,用来dbug的,但是注意代码运行时是不会有输出的*/
    int m = 1 ;
    while ( cin >> t && t != EOF )
    {
        memset(ans,0,sizeof(ans)) ;
        memset(vis,0,sizeof(vis)) ;
        //清空数组好习惯
        ans[1] = 1 ;//第一层的数一定是1,所以直接放进ans数组 
        vis[1] = 1 ;//标记 
        if ( m >= 2 ) cout << endl ;//从第二组数据开始才会每一个数据之间输出换行 
        cout << "Case " << m << ":" << endl ;
        dfs(2) ;//从第二层开始搜索 
        m++ ;
    }

    return 0 ;

}