_风休住 的博客

_风休住 的博客

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

posted on 2018-11-22 18:45:50 | under 题解 |

模拟构造回文素数

这道题本来是随便打表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;
}