USACO Section1.4 Arithmetic Progressions 解题报告

　　　　ariprog解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　找出所有在双平方数集合S中长度为N的等差数列。
　　双平方数集合S：所有能表示成p²+q²的数的集合，其中0<=p,q<=M。
【数据范围】
　　3<=N<=25
　　1<=M<=250
【输入格式】
　　N
　　M
【输出格式】
　　没找到数列，输出“NONE”。
　　找到数列了，就输出所有数列，每个数列占一行，格式为“a b”，a为首项、b为公差。
　　输出顺序：先按b升序，再按a升序。
【输入样例】
　　5
　　7
【输出样例】
　　1 4
　　37 4
　　2 8
　　29 8
　　1 12
　　5 12
　　13 12
　　17 12
　　5 20
　　2 24
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　先把S求出来。
　　然后以其中任何一个数a为首项，任何一个比a大的数b为第二项，便可得到一个等差数列。再数到第N项，若此N项均在集合S中，则此数列合法。
　　最后将所有数列按照题目要求排序，输出即可。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　第一次提交，卡在了第7个点上，运行时错误。
　　　　拿来数据一试，发现本机运行时间1.5s，看来算法需要改进。
　　　　把我的ok函数中*改成+，时间变为1s，不大保险，继续改进。（不过继续改进暂时没思路，先交上去看看……）
　　　　这次发现自己又粗心了！OJ上并未说我超时，我的代码只被运行了0.003s就停了，就是单纯的运行时错误！
　　　　不过本机运行没报错……看了会儿代码找不到越界，先去吃饭～
　　　　去吃饭路上想到哪儿错了～果然是有个地方数组下标越界，严谨性还是太差啊！
　　第二次提交，AC。
　　　　原来这题时间限制不是1s啊……2.2s也能过，我多虑了……

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

【代码】

 /*

 ID: icedrea1

 PROB: ariprog

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 const int maxd = ;

 int N,M;

 bool d[+maxd];

 int L;

 int num[maxd]; // maxd只是随便写的

 int l;

 struct Result

 {

     int a,b;

     friend bool operator<(Result const &x,Result const &y) { return x.b<y.b || x.b==y.b && x.a<y.a; }

 }A[];

 bool ok(int a,int b)

 {

     //cout<<"a="<<a<<"\tb="<<b<<endl;

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

     {

         a+=b;

         if(a>maxd || !d[a]) return false;

     }

     return true;

 }

 void qsort(int l,int r) // 注意，这里的l和全局的l并存，不会有错误～

 {

     if(l>=r) return;

     int i=l,j=r;

     Result x=A[(l+r)>>];

     while()

     {

         while(A[i]<x) ++i;

         while(x<A[j]) --j;

         if(i>j) break;

         swap(A[i],A[j]);

         ++i; --j;

     }

     qsort(l,j); qsort(i,r);

 }

 int main()

 {

     ifstream in("ariprog.in");

     ofstream out("ariprog.out");

     in>>N>>M;

     for(int p=;p<=M;++p)

         for(int q=p;q<=M;++q) d[p*p+q*q]=true;

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

         if(d[i]) num[++L]=i;

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

     {

         int a=num[i];

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

         {

             int b=num[j]-a;

             if(ok(a,b))

             {

                 ++l; A[l].a=a; A[l].b=b;

                 //cout<<"A=("<<a<<","<<b<<")"<<endl; cin.get();

             }

         }

     }

     qsort(,l);

     if(!l) out<<"NONE"<<endl;

     else for(int i=;i<=l;++i) out<<A[i].a<<" "<<A[i].b<<endl;

     in.close();

     out.close();

     return ;

 }

巴特西

USACO Section1.4 Arithmetic Progressions 解题报告

最新文章

热门文章