题解 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; } ```