USACO Section1.5 Prime Palindromes 解题报告

　　　　pprime解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　求a到b之间的所有回文素数（即又是素数又是回文数的数）。
【数据范围】
　　5<=a,b<=100,000,000
【输入样例】
　　5 500
【输出样例】
　　5
　　7
　　11
　　101
　　131
　　151
　　181
　　191
　　313
　　353
　　373
　　383
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　筛法求素数+回文数判断。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　第一个点就卡住了，运行时错误。
　　题目开始出现大数据了，以后要在交之前测试一下边界情况。
　　本机测试没问题，经过多次OJ上测试，得出是定义数组的大小问题。数据给出b的最大值的是100,000,000，但若我bool数组建这么大，会爆运行时错误。
　　我的解决办法是，实测满足条件的最大数maxd=9,989,899，于是数组范围定义为d[0~maxd]，AC了……
　　本题问题在于，我对USACO不甚了解。我查了USACO的内存限制，程序所用内存不能超过16M。
　　maxd=9,989,899时，所占内存约为10/8=1.25M，肯定没问题。
　　maxd=100,000,000时，所占内存约为100/8=12.5M，应该不超内存的；而USACO上面显示，我的代码运行0.000s时，使用了312KB的内存，这个看来自然是不可信……不知道为什么会超内存，好奇怪，这是为什么？在此向大家请教，希望知道的同学不吝赐教，多谢！

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

 /*

 ID: icedrea1

 PROB: pprime

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 const int maxd = ;

 //const int maxd = 100000000;

 int a,b;

 bool d[+maxd];

 int bit[],l;

 bool isPal(int x)

 {

     l=;

     while(x) { bit[++l]=x%; x/=; }

     for(int i=;i<=(l>>);++i)

         if(bit[i]!=bit[l+-i]) return false;

     return true;

 }

 int main()

 {

     ifstream in("pprime.in");

     ofstream out("pprime.out");

     d[]=d[]=true;

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

         if(!d[i])

             for(int j=i+i;j<=maxd;j+=i) d[j]=true;

     in>>a>>b;

     for(int i=a;i<=b;++i)

         if(i<=maxd && !d[i] && isPal(i)) out<<i<<endl;

     in.close();

     out.close();

     return ;

 }

巴特西

USACO Section1.5 Prime Palindromes 解题报告

最新文章

热门文章