洛谷题解 P1217 【[USACO1.5]回文质数 Prime Palindromes】

模拟构造回文素数

这道题本来是随便打表A掉的，但这实在不符合我的水准，于是想出了这份代码。
打表过的要脸么

刚拿到这题，首先想到暴力枚举。但看到数据规模似乎并不是很友好，只得作罢。。。

这时发现题目所述回文数一条神奇的性质：**当确定回文数的前半段时，该回文数的后半段也随之确定。**于是顿时想到可以通过枚举回文数的前半部分，生成其后半部分，然后判断它是否为素数，最后输出。

在枚举前半段回文数时，利用递归函数在fig数组中依次填数。当枚举完前半段后，再将后半段回文数补充完整。模拟过程如下图：

可以发现，无论要生成的回文数长度为多少，fig[(size+1)/2] 中总填入前半段回文数的最后一个数。当递归函数填至下一个格子中时，便可将前半段回文数反转后复制到后半段数组中。代码实现如下：

void DFS(int size,int now)
{
    if(now<=(size+1)/2)
        for(register int i=0;i<=9;++i)
        {
            if(now==1&&(i==0||i%2==0)) continue;//fig[1]中的数不能为0或偶数
            fig[now]=i;
            DFS(size,now+1);
            if(flag==false) return;
        }
    else
    {
        for(register int i=now;i<=size;++i) fig[i]=fig[size-i+1];
    }
}

在生成一个回文数之后，调用函数将fig数组标识的数提取出来，再判断其是否为素数。如果是素数，则输出，满足题目按字典序输出的要求。

由于构造回文数时只需枚举前半部分回文数，因此时间效率大大提高。这才叫高性能好不

标程：

#include<bits/stdc++.h>
using namespace std;
int A,B;
int fig[15]; 
bool flag=true;

int GetFig(int size)
{
    int ans=0;
    for(register int i=1;i<=size;++i)
    {
        ans*=10;
        ans+=fig[i];
    }
    return ans;
}

bool PrimeIf(int k)
{
    for(register int i=2;i<=sqrt(k);++i) 
        if(k%i==0) return false;
    return true;
}

void DFS(int size,int now)
{
    if(now<=(size+1)/2)
        for(register int i=0;i<=9;++i)
        {
            if(now==1&&(i==0||i%2==0)) continue;
            fig[now]=i;
            DFS(size,now+1);
            if(flag==false) return;
        }
    else
    {
        for(register int i=now;i<=size;++i) fig[i]=fig[size-i+1];
        int num=GetFig(size);
        if(num<A) return;
        if(num>B)
        {
            flag=false;
            return;
        }
        if(PrimeIf(num)) cout<<num<<endl;
        return; 
    }
}

int main()
{
    cin>>A>>B;
    for(register int i=1;i<=9;++i) DFS(i,1);
 	return 0;
}