洛谷P1217回文质数-Prime Palindrome回溯

P1217 [USACO1.5]回文质数 Prime Palindromes

题意：给定一个区间，输出其中的回文质数；

学习了洛谷大佬的回溯写法，感觉自己写回溯的能力不是很强；

#include <cstdio>

#include <iostream>

#include <cmath>

const int maxn = ;

using namespace std;

int a[maxn],l,r;

bool is_prime(int n)    //判断素数

{

    int x = sqrt(n);

    for(int i=;i<=x;i++)

    {

        if(n%i==)return false;

    }

    return true;

}

void dfs(int n,int t)

{

    if(t>(n+)/)            //如果当前已有的数字可以构成回文串；就接下去做

    {

        int s = ;

        for(int i=;i<=n/;i++)

        {

            a[n-i+] = a[i];        //制作回文

        }

        for(int i=;i<=n;i++)

        {

            s = s* + a[i];        //把数组汇总成数字；

        }

        if(s<l||s>r)return;            //不符合要求则return

        if(is_prime(s))

            cout<<s<<endl;            //若为素数则输出

    }

    else

    {

        for(int i=(t==);i<=;i+=(t==)+)        //一个一个进行放

        {                            //这里有个操作：若放的数字还是个位数字，就只能从1开始，每次加2；若不是个位，从0开始，每次加1；

            a[t]=i;

            dfs(n,t+);

        }

    }

}

int main(){

    ios::sync_with_stdio();

    cin.tie();

    cout.tie();

    cin>>l>>r;

    for(int i=ceil(log10(l));i<=ceil(log10(r));i++)//对各个位数的回文素数进行搜索，ceil(log10(r))是r的位数

        dfs(i,);

    return ;

}